#include <stdio.h>
#define Nmax 100000+2
#define INF 2147000000
#define LL long long
LL A[Nmax*4],B[Nmax*4],C[Nmax*4],S[Nmax*4];
int v[Nmax];
int N,M;
LL sum,s;
inline LL Maxim(LL x,LL y){ return x>y ? x:y; }
void Update(int nod,int l,int r,int poz,int val){
if( l==r ){
A[nod]=B[nod]=C[nod]=S[nod]=val;
return;
}
int m=l+(r-l)/2;
if( poz<=m ) Update(2*nod,l,m,poz,val);
else Update(2*nod+1,m+1,r,poz,val);
A[nod]=Maxim(A[2*nod],S[2*nod]+A[2*nod+1]);
B[nod]=Maxim(B[2*nod+1],S[2*nod+1]+B[2*nod]);
C[nod]=Maxim(Maxim(C[2*nod],C[2*nod+1]),B[2*nod]+A[2*nod+1]);
C[nod]=Maxim(C[nod],Maxim(A[nod],B[nod]));
S[nod]=S[2*nod]+S[2*nod+1];
}
void Query(int nod,int l,int r,int x,int y){
if( x<=l && r<=y ){
if(s<0) s=0;
sum = Maxim(sum, Maxim(s+A[nod],C[nod]));
s = Maxim(s+S[nod], B[nod]);
return;
}
int m=l+(r-l)/2;
if( x<=m ) Query(2*nod,l,m,x,y);
if( m <y ) Query(2*nod+1,m+1,r,x,y);
}
int main(){
int i,x,y;
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]);
Update(1,1,N,i,v[i]);
}
for(i=1;i<=M;++i){
scanf("%d%d",&x,&y);
sum=s=-INF;
Query(1,1,N,x,y);
printf("%lld\n",sum);
}
fclose(stdin); fclose(stdout);
return 0;
}