#include<fstream>
using namespace std;

struct a{
       long long sgen,sleft,sright,smax;
       }A[300050];      
long long val,st,dr,pos,MM,scur;
long long z[100005];
      
inline long long max(long long a,long long 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=z[left];
     return ;
                     }
     int div=(left+right)>>1;
     update(2*nod,left,div);
     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].sright)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;
    fin>>n>>m;
    for(i=1;i<=n;++i)fin>>z[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;   
}