#include<stdio.h>
int i,j,n,m,x,y;
long long sol,s;
int v[1000000];
long long a[1000000],b[1000000],c[1000000],sum[1000000];
long long maxim(long long a,long long b)
{
if(a>b)
return a;
return b;
}
void build(int nod,int li,int ls)
{
int mij=(li+ls)/2,st=nod*2,dr=st+1;
if(li==ls)
{
a[nod]=v[li];
b[nod]=v[li];
c[nod]=v[li];
sum[nod]=v[li];
}
else
{
build(st,li,mij);
build(dr,mij+1,ls);
a[nod]=maxim(a[st],sum[st]+a[dr]);
b[nod]=maxim(b[dr],sum[dr]+b[st]);
c[nod]=maxim(maxim(c[st],c[dr]),b[st]+a[dr]);
sum[nod]=sum[st]+sum[dr];
}
}
void query(int nod,int li,int ls)
{
int mij=(li+ls)/2,st=nod*2,dr=st+1;
if(x<=li&&y>=ls)
{
sol=maxim(maxim(a[nod],s+a[nod]),maxim(sol,c[nod]));
s=maxim(b[nod],s+sum[nod]);
}
else
{
if(x<=mij)
query(st,li,mij);
if(y>mij)
query(dr,mij+1,ls);
}
}
int main(void)
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d",&v[i]);
build(1,1,n);
i=i;
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
s=-32099;
sol=-32044;
query(1,1,n);
printf("%lld\n",sol);
}
return 0;
}