#include <fstream>

using namespace std;
ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct Nod{
    long long maxim,st,dr,sum;
}aint[400001];
Nod best(Nod left, Nod right){
    Nod rez;
    rez.sum = left.sum + right.sum;
    rez.st = max(left.st,left.sum + right.st);
    rez.dr = max(right.dr,right.sum + left.dr);
    rez.maxim = max(left.maxim,max(right.maxim,max(rez.st,max(rez.dr,left.dr + right.st))));
    return rez;
}
void update(long long nod,long long st,long long dr,long long poz,long long val){
    if(st == dr){
        aint[nod].sum =aint[nod].dr = aint[nod].st = aint[nod].maxim= val;
        return;
    }
    long long mid = st + dr;
    mid /= 2;
    if(poz <= mid){
        update(nod * 2,st,mid,poz,val);
    }else{
        update(nod * 2 + 1,mid + 1,dr,poz,val);
    }
    aint[nod] = best(aint[nod * 2],aint[nod * 2 + 1]);
}
Nod query(long long nod,long long st,long long dr,long long a, long long b){
    if(a <= st && dr <= b){
        return aint[nod];
    }
    long long mid = st + dr;
    mid /= 2;
    if(a <= mid && b > mid)
        return best(query(nod * 2,st,mid,a,b),query(nod * 2 + 1,mid + 1,dr,a,b));
    else if(a <= mid)
        return query(nod * 2,st,mid,a,b);
    else if(b > mid)
        return query(nod * 2 + 1,mid + 1,dr,a,b);
}
int main()
{
    long long n,m,x,y,i;
    cin >> n >> m;
    for(i = 1;i <= n;i++){
        cin >> x;
        update(1,1,n,i,x);
    }
    for( i= 1;i <= m;i++){
        cin >> x >> y;
        cout << query(1,1,n,x,y).maxim << "\n";
    }
    return 0;
}