#include <bits/stdc++.h>
#define MAXN 100000
#define MAXVAL 10000000000

using namespace std;

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

struct node{
    long long pref, suff, best, sum;
} aint[4 * MAXN];
int v[MAXN + 1];

node combine(node A, node B){
    node rez;

    rez.pref = max(A.pref, A.sum + B.pref);
    rez.suff = max(B.suff, B.sum + A.suff);
    rez.sum = A.sum + B.sum;
    rez.best = max(max(A.best, B.best), A.suff + B.pref);
    return rez;
}

void build(int nod, int st, int dr){
    int mij;

    if(st == dr){
        aint[nod].best = aint[nod].pref = aint[nod].suff = aint[nod].sum = v[st];
    }else{
        mij = (st + dr) / 2;
        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);

        aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
    }
}
node query(int nod, int st, int dr, int a, int b){
    int mij;
    node as, ad;

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

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

    return combine(as, ad);
}


int main()
{
    int n, m, i, x, y;

    fin >> n >> m;
    for(i = 1; i <= n; i++){
        fin >> v[i];
    }
    build(1, 1, n);

    while(m--){
        fin >> x >> y;
        node rez = query(1, 1, n, x, y);
        fout << rez.best << "\n";
    }
    return 0;
}