#include <stdio.h>

#define Nmax 100001

struct arbore { long long v,st,dr,all; };

int N,M,X,x,y,i;
long long nr,left;
arbore A[3*Nmax];

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

void update(int nod,int st,int dr,int who,int v)
{
 int m=(st+dr)>>1;

 if (st==dr)
    {
     A[nod].v=A[nod].st=A[nod].dr=A[nod].all=v;
     return;
    }
    
 if (who<=m) update(nod<<1,st,m,who,v);
    else update((nod<<1)+1,m+1,dr,who,v);
 
 A[nod].v+=v;
 A[nod].st=max(A[nod<<1].st,A[nod<<1].v+A[(nod<<1)+1].st);
 A[nod].dr=max(A[(nod<<1)+1].dr,A[nod<<1].dr+A[(nod<<1)+1].v);
 A[nod].all=max(A[nod<<1].dr+A[(nod<<1)+1].st,max(A[nod<<1].all,A[(nod<<1)+1].all));
}

void query(int nod,int st,int dr,int x,int y)
{
 int m=(st+dr)>>1;
 if (x<=st && y>=dr)
    {
     nr=max(nr,max(left+A[nod].st,A[nod].all));
     left=max(left+A[nod].v,A[nod].dr);
     return;
    }
 if (x<=m) query(nod<<1,st,m,x,y);
 if (y>m) query((nod<<1)+1,m+1,dr,x,y);  
}

int main()
{
 freopen("sequencequery.in","r",stdin);
 freopen("sequencequery.out","w",stdout);
 scanf("%d %d",&N,&M);
 for (i=1;i<=N;++i)
     {
      scanf("%d",&X);
      update(1,1,N,i,X);
     }
 while (M)
       {
        --M;
        scanf("%d %d",&x,&y);
        nr=left=-(0x3f3f3f3f);
        query(1,1,N,x,y);
        printf("%lld\n",nr);
       }    
 fclose(stdout);
 return 0;
}