#include <fstream>

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

const int NMAX = 100001, INF = 1e9;
struct node{
    int sum = -INF, prefix = -INF, suffix = -INF, max = -INF;
} ai[NMAX * 4];
int n, v[NMAX], q;

void build(int nod, int st, int dr){
    if(st == dr){
        ai[nod].max = ai[nod].prefix = ai[nod].suffix = ai[nod].sum = v[st];
        return;
    }

    int mij = (st + dr) / 2;
    build(2 * nod, st, mij);
    build(2 * nod + 1, mij + 1, dr);

    ai[nod].sum = ai[nod * 2].sum + ai[nod * 2 + 1].sum;
    ai[nod].prefix = max(ai[nod * 2].prefix, ai[nod * 2].sum + ai[nod * 2 + 1].prefix);
    ai[nod].suffix = max(ai[nod * 2 + 1].suffix, ai[nod * 2 + 1].sum + ai[nod * 2].suffix);
    ai[nod].max = max(ai[nod].prefix, max(ai[nod].suffix, max(ai[nod * 2].max, max(ai[nod * 2 + 1].max, ai[nod * 2].suffix + ai[nod * 2 + 1].prefix))));
}

node query(int nod, int st, int dr, int a, int b){
    node result;

    if(a <= st && b >= dr) return ai[nod];

    int mij = (st + dr) / 2;
    if(a > mij) return query(nod * 2 + 1, mij + 1, dr, a, b);
    if(b <= mij) return query(nod * 2, st, mij, a, b);

    node left = query(nod * 2, st, mij, a, b), right = query(nod * 2 + 1, mij + 1, dr, a, b);

    result.sum = left.sum + right.sum;
    result.prefix = max(left.prefix, left.sum + right.prefix);
    result.suffix = max(right.suffix, right.sum + left.suffix);
    result.max = max(result.prefix, max(result.suffix, max(left.max, max(right.max, left.suffix + right.prefix))));
    return result;
}

int main()
{
    fin >> n >> q;
    for(int i = 1; i <= n; i++) fin >> v[i];
    build(1, 1, n);
    for(int i = 1; i <= q; i++){
        int x, y;
        fin >> x >> y;
        node res = query(1, 1, n, x, y);
        fout << res.max << '\n';
    }
    return 0;
}