#include <fstream>

using namespace std;

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

typedef long long ll;
const int N=100000+5;

struct AINT
{
    ll best;
    ll st;
    ll dr;
    ll sum;
};

AINT a[3*N];

void update(ll nod,ll st,ll dr,ll poz,ll val) {
    if(st==dr) {
        a[nod].best=val;
        a[nod].st=val;
        a[nod].dr=val;
        a[nod].sum=val;
        return;
    }
    ll med=(st+dr)/2;
    if(poz<=med) {
        update(2*nod,st,med,poz,val);
    }
    else {
        update(2*nod+1,med+1,dr,poz,val);
    }
    a[nod].sum=a[2*nod].sum+a[2*nod+1].sum;
    a[nod].st=max(a[2*nod].st,a[2*nod].sum+a[2*nod+1].st);
    a[nod].dr=max(a[2*nod+1].dr,a[2*nod+1].sum+a[2*nod].dr);
    a[nod].best=max(max(a[2*nod].best,a[2*nod+1].best),a[2*nod].dr+a[2*nod+1].st);
}

ll best,s2;

void slove(ll nod,ll st,ll dr,ll x,ll y) {
    if(x<=st && dr<=y) {
        best=max(best,a[nod].best);
        best=max(best,s2+a[nod].st);
        s2=max(s2+a[nod].sum,a[nod].dr);
    }
    else {
        ll med=(st+dr)/2;
        if(x<=med) {
            slove(2*nod,st,med,x,y);
        }
        if(y>=med+1) {
            slove(2*nod+1,med+1,dr,x,y);
        }
    }
}

int main() {
    int n,q;
    fin>>n>>q;
    for(int i=1;i<=n;i++) {
        int x;
        fin>>x;
        update(1,1,n,i,x);
    }
    while(q--) {
        int st,dr;
        fin>>st>>dr;
        best=-(1LL<<60);
        s2=0;
        slove(1,1,n,st,dr);
        fout<<best<<"\n";
    }
    return 0;
}
/**



**/