#include<fstream>
using namespace std;

struct a{
       int sgen,sleft,sright,smax;
       }A[400050],sol;
int val,st,dr,pos,MM,scur;
      
inline int max(int a,int b){ return a>b?a:b; }
      
void update(int nod,int left,int right){
     if(left==right){
     A[nod].sgen = A[nod].sleft=A[nod].sright=A[nod].smax=val;
     return ;
                     }
     int div=(left+right)>>1;
     if(pos<=div)update(2*nod,left,div);
            else update(2*nod+1,div+1,right);
     
     A[nod].sleft = max(A[2*nod].sleft , A[2*nod].sgen+A[2*nod+1].sleft);
     
     A[nod].sright = max(A[2*nod].sright+A[2*nod+1].sgen , A[2*nod+1].sright);
     
     A[nod].sgen = A[2*nod].sgen + A[2*nod+1].sgen;
     
     A[nod].smax = max( A[2*nod].sright + A[2*nod+1].sleft , max(A[2*nod].smax , A[2*nod+1].smax) );
     
     }
   
void query(int nod,int left,int right){
     if(st<=left && right<=dr)
      {
       if(scur+A[nod].sleft>A[nod].smax)MM=max(scur+A[nod].sleft,MM);
                                    else MM=max(A[nod].smax,MM);
       if(scur+A[nod].sgen>A[nod].sgen)scur+=A[nod].sgen;
                                  else scur=A[nod].sright;  
       return;         
      }
     int div=(left+right)>>1;
     if(st<=div)query(2*nod,left,div);
     if(div<dr)query(2*nod+1,div+1,right);
         
     }
       
int main(void){
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    int n,m,i,j;
    fin>>n>>m;
    for(i=1;i<=n;++i)
    {
     fin>>val; pos=i;
     update(1,1,n);                 
    }
    for(i=1;i<=m;++i)
    {
     fin>>st>>dr; scur=0; MM=-111111;
     query(1,1,n);
     fout<<MM<<'\n';                
    }
   
 return 0;   
}