# include <stdio.h>
# define FIN "sequencequery.in"
# define FOUT "sequencequery.out"
# define max(a,b) (a>b?a:b)
# define MAXN 100005
# define ll long long
ll N,M,i,j,a,b,rez,mx,sum;
int V[MAXN];
ll S[MAXN];
ll A[1<<20];
ll B[1<<20];
ll C[1<<20];
void update(ll nod,ll st,ll dr,ll poz,ll vl)
{
ll 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(ll nod,ll st,ll dr,ll a,ll b)
{
ll 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("%lld%lld",&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("%lld\n",rez);
}
return 0;
}