# include <stdio.h>

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

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

    void update(int nod,int st,int dr,int poz,int vl)
    {
        int mij;
        if (st == dr)
          A[nod] = B[nod] = C[nod] = vl;
        else
          {
             mij = (st + dr) >> 1;
             if (poz <= mij) 
               update(nod<<1,st,mij,poz,vl);
             else
               update((nod<<1)+1,mij+1,dr,poz,vl);
             A[nod] = max(A[(nod<<1)+1],A[nod<<1]);
             B[nod] = max(B[nod<<1],S[mij]-S[st-1]+B[(nod<<1)+1]);
             C[nod] = max(C[(nod<<1)+1],S[dr]-S[mij]+C[nod<<1]);
             A[nod] = max(A[nod],C[nod<<1]+B[(nod<<1)+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]);
            sum = max(C[nod],S[dr]-S[st-1]+sum);
            rez = max(rez,sum);            
          }
        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];
          
        for (i = 1; i <= N; ++i)
          update(1,1,N,i,V[i]);
          
        for (i = 1; i <= M; ++i)
          {
             scanf("%d%d",&a,&b);
             rez = -100000;
             sum = 0;
             query(1,1,N,a,b);
             printf("%d\n",rez);
          }
                  
        return 0;
    }