#include <cstdio>
#define max(a,b) (a>b ? a:b)
const int NMAX=262144;
long long a[NMAX],beg[NMAX],end[NMAX],s[NMAX],maxim,sum;
int n,m,v[200002];
void Build(int vf,int ls,int ld){
     if (ls==ld) a[vf]=beg[vf]=end[vf]=s[vf]=v[ls];
     else{
      int mij=(ls+ld)/2;
      Build(2*vf,ls,mij);
      Build(2*vf+1,mij+1,ld);  
      beg[vf]=max(beg[2*vf],s[2*vf]+beg[2*vf+1]);  
      end[vf]=max(s[2*vf+1]+end[2*vf],end[2*vf+1]);
      a[vf]=max(max(a[2*vf],a[2*vf+1]),end[2*vf]+beg[2*vf+1]);
      s[vf]=s[2*vf]+s[2*vf+1];
      }
    }     
void Query(int vf,int ls,int ld,int l,int r){
     if (l<=ls && ld<=r) {
               maxim=max(maxim,max(sum+beg[vf],a[vf]));
               sum=max(s[vf]+sum,end[vf]);
                         }
       else{
     int mij=(ls+ld)/2;
     if (l<=mij) Query(2*vf,ls,mij,l,r);
     if (r>mij) Query(2*vf+1,mij+1,ld,l,r);}
     }
int main(){
    int b,c,i;
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (i=1;i<=n;++i) scanf("%d",&v[i]);
    Build(1,1,n);
     while (m--){
          scanf("%d %d",&b,&c);
          maxim=-999999999;
          sum=0;
          Query(1,1,n,b,c);
          printf("%lld\n",maxim);
          }
    return 0; 
}