#include<fstream>
#define DIM 100005
using namespace std;
int n, m, i, x, y;
int v[DIM];
struct snod{
    long long suma, sst, sdr, maxim;
};
snod a[4 * DIM], r;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
void build(int nod, int st, int dr){
    if(st == dr){
        a[nod].suma = a[nod].sst = a[nod].sdr = a[nod].maxim = v[st];
    }
    else{
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        a[nod].suma = a[2 * nod].suma + a[2 * nod + 1].suma;
        a[nod].sst = max(a[2 * nod].sst, a[2 * nod].suma + a[2 * nod + 1].sst);
        a[nod].sdr = max(a[2 * nod + 1].sdr, a[2 * nod].sdr + a[2 * nod + 1].suma);
        a[nod].maxim = max(a[2 *nod].sdr + a[2 * nod + 1].sst, max(a[2 * nod].maxim, a[2 * nod + 1].maxim) );
    }
}
snod query(int nod, int st, int dr, int x, int y){
    if(x <= st && dr <= y){
        return a[nod];
    }
    else{
        int mid = (st + dr) / 2;
        snod left, right;
        int ok1 = 0, ok2 = 0;
        if(x <= mid){
            ok1 = 1;
            left = query(2 * nod, st, mid, x, y);
        }
        if(y > mid){
            ok2 = 1;
            right = query(2 * nod + 1, mid + 1, dr, x, y);
        }
        if(ok2 == 0){
            return left;
        }
        else{
            if(ok1 == 0){
                return right;
            }
            else{
                snod r;
                r.suma = left.suma + right.suma;
                r.sst = max(left.sst, left.suma + right.sst);
                r.sdr = max(right.sdr, right.suma + left.sdr);
                r.maxim = max(left.sdr + right.sst, max(left.maxim, right.maxim) );
                return r;
            }
        }
    }
}
int main(){
    fin>> n >> m;
    for(i = 1; i <= n; i++){
        fin>> v[i];
    }
    build(1, 1, n);
    for(i = 1; i <= m; i++){
        fin>> x >> y;
        r = query(1, 1, n, x, y);
        fout<< r.maxim <<"\n";
    }
    return 0;
}