#include<stdio.h>
#define NMAX 100001
#define inf 6000000000LL
const int q=(NMAX<<1)+(NMAX<<1);
long long SUM[q],L[q],R[q],SOL[q];
int pos;
long long val;
int l1,l2;
long long ANS,D;

inline long long max(const long long a,const long long b){ return a>b?a:b; }

void update_1(const int nod,const int left,const int right)
{
     if( left==right )
     {
         SUM[nod]=L[nod]=R[nod]=SOL[nod]=val;
         return;
     }
     
     int mij=(left+right)>>1;
     int aux=nod<<1;
     if( pos<=mij ) 
         update_1( aux, left, mij);   
     else
         update_1( aux+1, mij+1, right );

     SUM[nod]=SUM[aux]+SUM[aux+1];
     L[nod]=max(L[aux], SUM[aux]+L[aux+1] );
     R[nod]=max(R[aux+1], SUM[aux+1]+R[aux] );
     SOL[nod]=max( max( SOL[aux], SOL[aux+1]), R[aux]+L[aux+1] );
}

void query(const int nod,const int left,const int right)
{
     if( left>=l1 && l2>=right )
     {
         ANS=max( max(ANS, SOL[nod]), D+L[nod] );
         D=max( R[nod], SUM[nod]+D );
         //printf(" nod %d ANS %d D %d L[nod] %d R[nod] %d l1 %d l2 %d\n",nod,ANS,D,L[nod],R[nod],l1,l2);
         return;
     }
     if( right<l1 || left>l2 || right==left )
         return;
     
     int mij=(left+right)>>1;
     int aux=nod<<1;
     query(aux,left,mij);
     query(aux+1,mij+1,right);

}
          
int main()
{
    freopen("sequencequery.in","r",stdin);
    freopen("sequencequery.out","w",stdout);
    
    int N,Q;
    scanf("%d%d",&N,&Q);
    
    int i;
    long long a1;
    for(i=1; i<=N; ++i){
             scanf("%lld",&a1);
             pos=i; val=a1;
             update_1(1,1,N);
    }
    
    while( Q-- )
    {
           scanf("%d%d",&l1,&l2);
           ANS=-inf; D=-inf;
           query(1,1,N);
           printf("%lld\n",ANS);
    }
    
    return 0;
}