#include <cstdio>  
   
 #define MAX_N (1 << 20)  
   
 #define le (nod << 1)  
 #define rt (le + 1)  
 #define md ((li + lf) >> 1)  
   
 inline long long max(long long a, long long b)  
 {  
     return (a < b)? b : a;  
 }  
   
 long long A[MAX_N], B[MAX_N], C[MAX_N], Sum[MAX_N], V[MAX_N];  
 int N, M, st, dr;  
 long long S, Sol;  
   
 void build(int nod, int li, int lf)  
 {  
     if(li == lf)  
     {  
         A[nod] = B[nod] = C[nod] = Sum[nod] = V[li];  
         return;  
     }  
   
     build(le, li, md);  
     build(rt, md + 1, lf);  
   
     A[nod] = max(A[le], Sum[le] + A[rt]);  
     B[nod] = max(B[rt], Sum[rt] + B[le]);  
     C[nod] = max(max(C[rt], C[le]), A[rt] + B[le]);  
   
     Sum[nod] = Sum[rt] + Sum[le];  
 }  
   
 void query(int nod, int li, int lf)  
 {  
     if(li >= st && dr >= lf)  
     {  
         if(S < 0) S = 0;  
   
         Sol = max(Sol, max(S + A[nod], C[nod]));  
         S = max(S + Sum[nod], B[nod]);  
         return;  
     }  
   
     if(st <= md) query(le, li, md);  
     if(dr > md) query(rt, md+1, lf);  
 }  
   
 void citire()  
 {  
     scanf("%d %d",&N, &M);  
   
     for(int i = 1; i <= N; ++i)  
         scanf("%lld",V+i);  
   
     build(1, 1, N);  
 }  
   
 void solve()  
 {  
     for(int i = 1; i <= M; ++i)  
     {  
         scanf("%d %d\n",&st, &dr);  
   
         Sol = V[st], S = 0;  
         query(1, 1, N);  
   
         printf("%lld\n",Sol);  
     }  
 }  
   
 int main()  
 {  
     freopen("sequencequery.in","rt",stdin);  
     freopen("sequencequery.out","wt",stdout);  
   
     citire();  
     solve();  
}