#include <stdio.h>
#define Nmax 100000+2
#define INF 2147000000
#define LL long long

LL A[Nmax],B[Nmax],C[Nmax],S[Nmax];
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,LL 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]);
	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 ){
		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;
}