#include<stdio.h>
#define dim 100010

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

int V[dim],S[dim],n,m,a,b;

struct arbore{
	int b;
	int i;
	int e;
}A[3*dim];

struct intervale{
	int b;
	int i;
	int e;
	int t;
}aux;

inline void read(){
	int i;
	fscanf(f,"%d%d",&n,&m);
	for(i=1;i<=n;i++)
		fscanf(f,"%d",&V[i]),S[i]=S[i-1]+V[i];
}

inline int maxim(int x , int y , int z){
	int t=(x>y)?x:y;
	t=(t>z)?t:z;
	return t;
}

inline int maxim2(int x,int y){
	return (x>y)?x:y;
}

void update(int nod,int st,int dr){
	if(st==dr){
		A[nod].b=A[nod].i=A[nod].e=V[st];
		return;
	}
	int mij=(st+dr)/2;
	update(2*nod,st,mij);
	update(2*nod+1,mij+1,dr);
	A[nod].i=maxim(A[2*nod].i,A[2*nod+1].i,A[2*nod].e+A[2*nod+1].b);
	A[nod].b=maxim2(A[2*nod].b,S[mij]-S[st-1]+A[2*nod+1].b);
	A[nod].e=maxim2(A[2*nod+1].e,S[dr]-S[mij]+A[2*nod].e);
}

intervale querry(int nod,int st,int dr){
	intervale v1,v2,v3;
	int ok2=0,ok3=0;
	if(a<=st&&dr<=b){
		v1.b=A[nod].b;
		v1.i=A[nod].i;
		v1.e=A[nod].e;
		v1.t=S[dr]-S[st-1];
		return v1;
	}
	int mij=(st+dr)/2;
	if((a>=st&&a<=mij)||(b>=st&&b<=mij))
		v2=querry(2*nod,st,mij),ok2=1;;
	if((a>=(mij+1)&&a<=dr)||(b>=(mij+1)&&b<=dr))
		v3=querry(2*nod+1,mij+1,dr),ok3=1;
	if(ok2&&(!ok3))
		return v2;
	if(ok3&&(!ok2))
		return v3;
	v1.i=maxim(v2.i,v3.i,v2.e+v3.b);
	v1.b=maxim2(v2.b,v2.t+v3.b);
	v1.e=maxim2(v3.e,v3.t+v2.e);
	v1.t=v2.t+v3.t;
	return v1;
}

int main(){
	
	read();
	
	update(1,1,n);
	
	for(int i=1;i<=m;i++){
		fscanf(f,"%d%d",&a,&b);
		aux=querry(1,1,n);
		fprintf(g,"%d\n",aux.i);
	}
	
	return 0;
}