# include <stdio.h>
# define m 300001
int N,M,A,B,x,poz;
long SD[m],Sum[m],S[m],D[m];
long long Max,s;
long long max(long long a, long long b)
{
if (a>b) return a;
return b;
}
void Upd(int nod, int st, int dr)
{
int mij,l,r;
if (st==dr) SD[nod]=Sum[nod]=S[nod]=D[nod]=x;
else {
mij=(st+dr)/2; l=2*nod; r=l+1;
if (poz<=mij) Upd(l,st,mij);
else Upd(r,mij+1,dr);
S[nod]=max(S[l],Sum[l]+S[r]);
D[nod]=max(D[l]+Sum[r],D[r]);
SD[nod]=max(max(SD[l],SD[r]),D[l]+S[r]);
Sum[nod]=Sum[l]+Sum[r];
}
}
void Query(int nod, int st, int dr)
{
int mij,l,r;
if (A<=st && dr<=B){
Max=max(Max, max(s+S[nod],SD[nod]));
s=max(s+Sum[nod],D[nod]);
}
else {
mij=(st+dr)/2; l=2*nod; r=l+1;
if (A<=mij) Query(l,st,mij);
if (mij<B) Query(r,mij+1,dr);
}
}
int main()
{
int i;
freopen("sequencequery.in", "r", stdin);
freopen("sequencequery.out", "w", stdout);
scanf("%d %d", &N, &M);
for (i = 1; i <= N; i++ ){
scanf("%d", &x);
poz=i; Upd(1,1,N);
}
for (i = 1; i <= M; i++ ){
scanf("%d %d",&A, &B);
s=0; Max=-1000000000; Query(1,1,N);
printf("%lld\n", Max);
}
return 0;
}