#include<fstream>
#include<limits.h>
#define lim 100002
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
long long A[3*lim],B[3*lim],C[3*lim],S[3*lim],n,q,sumasub,suma,v[lim],a,b,i;
int max(int a,int b){
 if(a<b)
  return b;
 return a;
}
void build(int nod,int st,int dr ){
	if(st==dr){
		A[nod]=B[nod]=C[nod]=v[st];
	  S[nod]=v[st];
	}
	else{
		int mij=(st+dr)/2;
		build(2*nod,st,mij);
		build(2*nod+1,mij+1,dr);
     A[nod]=max(S[2*nod]+A[2*nod+1],A[2*nod]);
     B[nod]=max(B[2*nod]+S[2*nod+1],B[2*nod+1]);
     C[nod]=max(max(C[2*nod],C[2*nod+1]),A[2*nod+1]+B[2*nod]);
	  S[nod]=S[2*nod]+S[2*nod+1];
 }
}
void query(int nod,int st,int dr){
	if(a<=st && b>=dr){
		sumasub=max(sumasub,max(suma+A[nod],C[nod]));
		suma=max(suma+S[nod],B[nod]);
	 }
	else{
		int mij=(st+dr)/2;
		if(a<=mij)
		  query(2*nod,st,mij);
		if(b>mij)
			query(2*nod+1,mij+1,dr);
	}
}
int main (){
	f>>n>>q;
	for(i=1;i<=n;i++)
		f>>v[i];
	build(1,1,n);
	for(;q;q--){
		f>>a>>b;
		suma=0;
		sumasub=-INT_MAX;
		query(1,1,n);
		g<<sumasub<<"\n";
	}
 return 0;
}