#include <stdio.h>
#define Nmax 100000
struct arbore { int v,st,dr,all; };
int N,M,X,x,y,i,nr,left;
arbore A[3*Nmax];
inline int max(int a,int 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("%d\n",nr);
}
fclose(stdout);
return 0;
}