#include <stdio.h>
#define INF 1<<30
#define maxim(a,b) (((a)>(b))?(a):(b))
int poz,x,y;
long long s,MAX;
struct arb{int S,D,SD,sum;}A[30002];
void update(int nod,int l,int r){
if (l==r){A[nod].S=A[nod].D=A[nod].SD=A[nod].sum=x;return;}
int m=(l+r)>>1,fl=nod<<1,fr=fl|1;
if (poz<=m)update(fl,l,m);
else update (fr,m+1,r);
A[nod].S = maxim( A[fl].S, A[fl].sum + A[fr].S );
A[nod].D = maxim( A[fr].D, A[fl].S + A[fr].sum );
A[nod].SD =maxim( maxim( A[fr].SD, A[fr].SD), A[fl].D + A[fr].S );
}
void query(int nod,int l,int r){
if (x<=l&&r<=y){
MAX = maxim( MAX, maxim( s + A[nod].S, A[nod].SD));
s=maxim( s + A[nod].sum, A[nod].D);
return;
}
int m=(l+r)>>1;
if (x<=m)query(nod<<1,l,m);
if (m< y)query((nod<<1)|1,m+1,r);
}
int main(){
freopen("sequencequery.in","r",stdin); freopen("sequencequery.out","w",stdout);
int n,m,i;
scanf("%d %d",&n,&m);
for (i=1;i<=n;++i){poz=i;scanf("%d",&x);update(1,1,n);}
for (;m;--m){s=0;MAX=-INF;scanf("%d %d",&x,&y);query(1,1,n);printf("%lld\n",MAX);}
return 0;
}