#include <cstdio>
#include <cctype>
#define MAXBUF 1<<17
FILE*fi,*fout;
char buf[MAXBUF];
int pos=MAXBUF;
inline char nextch(){
    if(pos==MAXBUF){
        fread(buf,1,MAXBUF,fi);
        pos=0;
    }
    return buf[pos++];
}
inline int getnr(){
   char a=nextch();
   char sign=1;
   if(a=='-')
      sign=-1;
   while(isdigit(a)==0)
      a=nextch();
   int nr=0;
   while(isdigit(a)==1){
      nr=nr*10+a-'0';
      a=nextch();
   }
   return nr*sign;
}
#define MAXN 100000
#define INF 100000000000000000LL
struct Nod{
    long long ssm;
    long long prefix;
    long long sufix;
    long long sum;
    inline void reset(long long val){
        ssm=val;
        prefix=val;
        sufix=val;
        sum=val;
    }
};
Nod aint[4*MAXN+1];
inline long long getmax(long long a,long long b){
    if(a>b) return a;
    return b;
}
void update(int nod,int left,int right,int poz,int val){
     if(left==right)
        aint[nod].reset(val);
     else{
        int med=(left+right)/2;
        if(poz<=med)
          update(2*nod,left,med,poz,val);
        else
          update(2*nod+1,med+1,right,poz,val);
        aint[nod].ssm=getmax(getmax(aint[2*nod].ssm,aint[2*nod+1].ssm),aint[2*nod].sufix+aint[2*nod+1].prefix);
        aint[nod].prefix=getmax(aint[2*nod].prefix,aint[2*nod].sum+aint[2*nod+1].prefix);
        aint[nod].sufix=getmax(aint[2*nod+1].sum+aint[2*nod].sufix,aint[2*nod+1].sufix);
        aint[nod].sum=aint[2*nod].sum+aint[2*nod+1].sum;
     }
}
long long ans;
long long ssm;
void query(int nod,int left,int right,int l,int r){
     if(l<=left&&right<=r){
         ans=getmax(ans,getmax(aint[nod].ssm,getmax(aint[nod].prefix+ssm,aint[nod].sum+ssm)));
         ssm=getmax(aint[nod].sufix,ssm+aint[nod].sum);
     }
     else{
         int med=(left+right)/2;
         if(l<=med)
           query(2*nod,left,med,l,r);
         if(med<r)
           query(2*nod+1,med+1,right,l,r);
     }
}
int main(){
   int n,m,x,a,b,i;
   fi=fopen("sequencequery.in" ,"r");
   fout=fopen("sequencequery.out" ,"w");
   n=getnr();
   m=getnr();
   for(i=1;i<=4*n;i++)
     aint[i].reset(-INF);
   for(i=1;i<=n;i++){
     x=getnr();
     update(1,1,n,i,x);
   }
   while(m>0){
      m--;
      a=getnr();
      b=getnr();
      ans=-INF;
      ssm=-INF;
      query(1,1,n,a,b);
      fprintf(fout,"%lld\n" ,ans);
   }
   fclose(fi);
   fclose(fout);
   return 0;
}