#include<stdio.h>
#define Nmax 100005

FILE*f=fopen("sequencequery.in","r");
FILE*g=fopen("sequencequery.out","w");

int i,N,M,a,b,V[100005];
long long Rez,ss;

struct arb{
	int D;
	int S;
	int Tt;
	int Smax;
}A[4*Nmax];

long long max(int a,int b){
	if ( a > b )
		return a;
	return b;
}

void update(int nod,int st,int dr){
	if ( st == dr ){
		A[nod].D = A[nod].S = A[nod].Tt = A[nod].Smax = V[st];
		return ;
	}
	int nodst = nod << 1;
	int noddr = nodst + 1;
	int mj = st + ( dr - st ) / 2;
	update(nodst,st,mj);
	update(noddr,mj+1,dr);
	
	A[nod].Smax = max(A[nodst].D + A[noddr].S,max(A[nodst].Smax,A[noddr].Smax));
	A[nod].Tt = A[nodst].Tt + A[noddr].Tt;
	A[nod].D = max(A[noddr].D,max(A[nod].Tt,A[noddr].Tt + A[nodst].D));
	A[nod].S = max(A[nodst].S,max(A[nod].Tt,A[nodst].Tt + A[noddr].S));
}

void Query(int nod,int st,int dr){
	if ( a <= st && dr <= b ){
		Rez = max(Rez,max(A[nod].Smax, ss + A[nod].S ));
		ss = max(ss + A[nod].Tt , A[nod].D);
		return ;
	}
	int nodst = nod << 1;
	int noddr = nodst + 1;
	int mj = st + ( dr - st ) / 2;
	
	if ( a <= mj ){
		Query(nodst,st,mj);
	}
	if ( b > mj ){
		Query(noddr,mj+1,dr);
	}
	
	
}

int main () {
	fscanf(f,"%d %d",&N,&M);
	for ( i = 1 ; i <= N ; ++i ){
		fscanf(f,"%d",&V[i]);
	}
	update(1,1,N);
	
	for ( i = 1 ; i <= M ; ++i ){
		fscanf(f,"%d %d",&a,&b);
		Rez = ss = -(1 << 30);
		Query(1,1,N);
		fprintf(g,"%lld\n",Rez);
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}