//#include <iostream>
#include <fstream>
using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct arbore{
    int suff,sum,pref,ma,rasp;
}aint[400005];

void add(int st,int dr,int nod,int poz,int val){
    if(dr<poz)
        return;
    if(st>poz)
        return;
    if(st==dr){
        aint[nod].sum=val;
        aint[nod].ma=val;
        aint[nod].pref=val;
        aint[nod].suff=val;
        aint[nod].rasp=val;
        if(val<0){
            aint[nod].pref=0;
            aint[nod].suff=0;
            aint[nod].rasp=0;
        }
        return;
    }
    add(st,(st+dr)/2,nod*2,poz,val);
    add((st+dr)/2+1,dr,nod*2+1,poz,val);
    aint[nod].sum=aint[nod*2].sum+aint[nod*2+1].sum;
    aint[nod].ma=max(aint[nod*2].ma,aint[nod*2+1].ma);
    aint[nod].pref=max(aint[nod*2].pref,aint[nod*2].sum+aint[nod*2+1].pref);
    aint[nod].suff=max(aint[nod*2].suff+aint[nod*2+1].sum,aint[nod*2+1].suff);
    aint[nod].rasp=max(aint[nod*2].suff+aint[nod*2+1].pref,max(aint[nod*2].rasp,aint[nod*2+1].rasp));
}
int prefix=0,maxim=0;
void query(int st,int dr,int nod,int ss,int dd){
    if(dr<ss)
        return;
    if(dd<st)
        return;
    if(ss<=st and dr<=dd){
        //cout<<st<<" "<<dr<<" ";
        maxim=max(maxim,prefix+aint[nod].pref);
        //cout<<prefix<<" ";
        prefix=max(prefix+aint[nod].sum,aint[nod].suff);
        //cout<<prefix<<"\n";
        maxim=max(maxim,aint[nod].rasp);
        //maxim=max(maxim,prefix);
        return;
    }
    query(st,(st+dr)/2,nod*2,ss,dd);
    query((st+dr)/2+1,dr,nod*2+1,ss,dd);
}
int query_max(int st,int dr,int nod,int ss,int dd){
    if(dr<ss)
        return -999999;
    if(dd<st)
        return -999999;
    if(ss<=st and dr<=dd){
        return aint[nod].ma;
    }
    return max(query_max(st,(st+dr)/2,nod*2,ss,dd),query_max((st+dr)/2+1,dr,nod*2+1,ss,dd));
}
int main()
{
    int n,m,a,b;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a;
        add(1,n,1,i,a);
    }
    //cout<<"\n";
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        prefix=0,maxim=0;
        int mm=query_max(1,n,1,a,b);
        //cout<<mm<<"\n";
        if(mm<0){
            cout<<mm<<"\n";
            continue;
        }
        query(1,n,1,a,b);
        cout<<maxim<<"\n";
    }
    return 0;
}