#include <bits/stdc++.h>

#define N_MAX 200000
#define ll long long

using namespace std;

int n, q;

struct Node
{
    int sum, prefMax, suffMax, subMax;
};

Node aint[N_MAX];

Node compute (Node lson, Node rson)
{
    Node ans;
    ans.sum = lson.sum + rson.sum;
    ans.prefMax = max(lson.prefMax, lson.sum + rson.prefMax);
    ans.suffMax = max(rson.suffMax, rson.sum + lson.suffMax);
    ans.subMax = max(lson.suffMax, rson.prefMax);
    ans.subMax = max(ans.subMax, lson.suffMax + rson.prefMax);
    ans.subMax = max(ans.subMax, max(lson.subMax, rson.subMax));
    return ans;
}

void update (int l, int r, int node, int qpos, int val)
{
    if(l == r)
    {
        aint[node-1].prefMax = aint[node-1].suffMax = aint[node-1].sum = aint[node-1].subMax = val;
        return;
    }
    int mid = (l + r) / 2, lson = (node << 1), rson = (lson + 1);
    if(qpos <= mid)
        update(l, mid, lson, qpos, val);
    else
        update(mid + 1, r, rson, qpos, val);
    aint[node-1] = compute(aint[lson-1], aint[rson-1]);
}

Node query (int l, int r, int node, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return aint[node-1];
    int mid = (l + r) / 2, lson = (node << 1), rson = (lson + 1);
    if(ql <= mid && mid + 1 <= qr)
    {
        Node lq = query(l, mid, lson, ql, qr);
        Node rq = query(mid + 1, r, rson, ql, qr);
        return compute(lq, rq);
    }
    else if(ql <= mid)
        return query(l, mid, lson, ql, qr);
    else if(mid + 1 <= qr)
        return query(mid + 1, r, rson, ql, qr);
}

int val;

int l, r;

int main()
{
    ifstream fin ("sequencequery.in");
    ofstream fout ("sequencequery.out");
    fin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        fin >> val;
        update(1, n, 1, i, val);
    }
    while(q--)
    {
        fin >> l >> r;
        fout << query(1, n, 1, l, r).subMax << "\n";
    }
    return 0;
}