#include <fstream>
using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

#define int long long

struct nod{
    int st,dr,a,sum;
} aint[400001];
int v[100001];

nod combin(nod a,nod b){
    nod rasp;
    rasp.a=max(max(a.a,b.a),a.dr+b.st);
    rasp.st=max(a.sum+b.st,a.st);
    rasp.dr=max(b.dr,b.sum+a.dr);
    rasp.sum=a.sum+b.sum;
    return rasp;
}

void init(int nod,int st,int dr){
    if(st==dr){
        aint[nod].st=aint[nod].dr=aint[nod].a=aint[nod].sum=v[st];
        return ;
    }
    int mij=(st+dr)/2;
    init(2*nod,st,mij);
    init(2*nod+1,mij+1,dr);
    aint[nod]=combin(aint[2*nod],aint[2*nod+1]);
}

nod query(int nod,int st,int dr,int a,int b){
    if(b<st || dr<a) return {(int)-1e18,(int)-1e18,(int)-1e18,0};
    if(a<=st && dr<=b) return aint[nod];
    int mij=(st+dr)/2;
    return combin(query(2*nod,st,mij,a,b),
                  query(2*nod+1,mij+1,dr,a,b));

}

signed main()
{
    int n,m,i,a,b;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        cin>>v[i];
    }
    init(1,1,n);
    for(i=1;i<=m;i++){
        cin>>a>>b;
        cout<<query(1,1,n,a,b).a<<"\n";
    }
    return 0;
}