# include <cstdio>

using namespace std;

# define FIN "sequencequery.in"
# define FOUT "sequencequery.out"
# define max(a,b) (a > b ? a : b)
# define MAXN 100005

int N,M,i,j,a,b;
long long rez,sum;
int V[MAXN];
long long S[MAXN];
long long A[MAXN*3];
long long B[MAXN*3];
long long C[MAXN*3];

     void update(int nod,int st,int dr)
     {
         int mij;
         
         if (st == dr)
           A[nod] = B[nod] = C[nod] = V[st];
         else
           {
               mij = (st + dr) >> 1;
               update(nod<<1,st,mij);
               update(nod<<1|1,mij+1,dr);
               A[nod] = max(A[nod<<1|1],A[nod<<1]);
               B[nod] = max(B[nod<<1],B[nod<<1|1]+S[mij]-S[st-1]);
               C[nod] = max(C[nod<<1|1],C[nod<<1]+S[dr]-S[mij]);
               A[nod] = max(A[nod],B[nod<<1|1]+C[nod<<1]);
           }
     }
     
     void query(int nod,int st,int dr,int a,int b)
     {
         int mij;
         
         if (a <= st && dr <= b)
           {
               rez = max(rez,A[nod]);
               if (sum < 0) sum = 0;
               rez = max(rez,sum + B[nod]);
               sum = max(C[nod],sum + S[dr] - S[st-1]);
           }
         else
           {
               mij = (st + dr) >> 1;
               if (a <= mij)
                 query(nod<<1,st,mij,a,b);
               if (b > mij)
                 query(nod<<1|1,mij+1,dr,a,b);
           }
     }

     int main()
     {
         freopen(FIN,"r",stdin);
         freopen(FOUT,"w",stdout);
         
         scanf("%d%d",&N,&M);
         for (i = 1; i <= N; ++i)
           {
              scanf("%d",&V[i]);
              S[i] = S[i-1] + V[i];
           }
         
         update(1,1,N);
           
         for (i = 1; i <= M; ++i)
           {
              sum = 0;
              rez = -100000;
              scanf("%d%d",&a,&b);
              query(1,1,N,a,b);
              printf("%lld\n",rez);
           }
            
         return 0;
     }