#include <algorithm>
#include <cstdio>
using namespace std;

int const maxn=100*1000,maxt=2*maxn-1,
cnst=5,log_maxn=20,maxr=cnst*log_maxn;

struct tree
{
int A[maxn],N;
// when x represents the interval [i..j],
// x.b = max { A[s]+...+A[t], i<=s<=t<=j },
// x.p = max { A[i]+...+A[s], i<=s<=j },
// x.s = max { A[t]+...+A[j], i<=t<=j }, and
// x.t = A[i]+...A[j].
struct segment{int b,p,s,t;};

segment T[maxt];

int inline c0(int n){return 2*(n+1)-1;}
int inline c1(int n){return 2*(n+1);}
int inline m0(int a,int b){return (a+b)/2;}
int inline m1(int a,int b){return (a+b)/2+1;}

void init(int n,int a,int b)
{	if(a==b)
	{T[n].b=T[n].p=T[n].s=T[n].t=A[a];return;}
	init(c0(n),a,m0(a,b));
	init(c1(n),m1(a,b),b);
	int n0=c0(n),n1=c1(n);
	T[n].b=max(T[n0].b,max(T[n1].b,T[n0].s+T[n1].p));
	T[n].p=max(T[n0].p,T[n0].t+T[n1].p);
	T[n].s=max(T[n1].s,T[n1].t+T[n0].s);
	T[n].t=T[n0].t+T[n1].t;
}

void init(){init(0,0,N);}

int X,Y,L,R[maxr];

void traversal(int n,int a,int b)
{	if((X<=a)&&(b<=Y))
	{R[L++]=n;return;}
	if(X<=m0(a,b)){traversal(c0(n),a,m0(a,b));}
	if(m1(a,b)<=Y){traversal(c1(n),m1(a,b),b);}
}

void buildRXY(int x,int y)
{X=x;Y=y;L=0;traversal(0,0,N);}

int query(int x,int y)
{	buildRXY(x,y);
	// case 1:
	int b=T[R[0]].b,i;
	for(i=1;L>i;++i)
	{if(T[R[i]].b>b){b=T[R[i]].b;}}
	// case 2:
	int v=T[R[0]].s,b1;
	for(i=1;L>i;++i)
	{	b1=v+T[R[i]].s;
		if(b<b1){b=b1;}
		v=max(v+T[R[i]].t,T[R[i]].s);
	}
	return b;
}

};

tree T;

int main()
{	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	int n,m,i,x,y,q;
	scanf("%d %d",&n,&m);
	for(i=0;n>i;++i){scanf("%d",T.A+i);}
	T.N=n-1;T.init();
	for(i=0;m>i;++i)
	{	scanf("%d %d",&x,&y);--x;--y;
		q=T.query(x,y);
		printf("%d\n",q);
	}
	return 0;
}