#include<stdio.h>
#define inf -2000000
#define Nmax 200010
#define Armax 600010
int vec[Nmax],n;
struct nod
{
	long long  l,r,o,s;
}ar[Armax];
//using namespace std;
long long max(long long a,long long b)
{
	if(a>b)	return a;
	return b;
}
void build(int poz,int p,int u)
{
	int mij;
	if(p==u)
		ar[poz].l=ar[poz].r=ar[poz].o=ar[poz].s=vec[p];
	else
	{
		mij=(p+u)/2;
		build(2*poz,p,mij);
		build(2*poz+1,mij+1,u);
		ar[poz].l=max(ar[2*poz].l,ar[2*poz].s+ar[2*poz+1].l);
		ar[poz].r=max(ar[2*poz+1].r,ar[2*poz+1].s+ar[2*poz].r);
		ar[poz].o=max(ar[2*poz+1].l+ar[2*poz].r,max(ar[2*poz+1].o,ar[2*poz].o));
		ar[poz].s=ar[2*poz].s+ar[2*poz+1].s;
	}
}

void update(int pl,int val,int poz,int p,int u)
{
	int mij;
	if(p==u)
		ar[poz].l=ar[poz].r=ar[poz].o=ar[poz].s=val;
	else
	{
		mij=(p+u)/2;
		if(pl<=mij)
			update(pl,val,2*poz,p,mij);
		else
			update(pl,val,2*poz+1,mij+1,u);
		ar[poz].l=max(ar[2*poz].l,ar[2*poz].s+ar[2*poz+1].l);
		ar[poz].r=max(ar[2*poz+1].r,ar[2*poz+1].s+ar[2*poz].r);
		ar[poz].o=max(ar[2*poz+1].l+ar[2*poz].r,max(ar[2*poz+1].o,ar[2*poz].o));
		ar[poz].s=ar[2*poz].s+ar[2*poz+1].s;
	}
	
}
void query(int c1,int c2,int poz,int p,int u,nod &v)
{
	int mij,aj1=0,aj2=0;
	nod v1,v2;
	if(p==u || (c1<=p && c2>=u))
			v=ar[poz];
	else
	{
		mij=(p+u)/2;
		if(c1<=mij && c2>=p)
		{	aj1=1;
			query(c1,c2,2*poz,p,mij,v1);
		}
		if(c2>mij && c1<=u)
		{	aj2=1;
			query(c1,c2,2*poz+1,mij+1,u,v2);
		}
		if(aj1 && aj2)
		{
			v.l=max(v1.l,v1.s+v2.l);
			v.r=max(v2.r,v2.s+v1.r);
			v.o=max(v1.r+v2.l,max(v1.o,v2.o));
			v.s=v1.s+v2.s;
		}	
		else
			if(aj1)
				v=v1;
			else
				v=v2;
	}
}

/*void afisare()
{
	int i;
	for(i=1;i<15 ;i++)
		printf("%d %d %d %d\n",ar[i].l,ar[i].r,ar[i].o,ar[i].s);
}*/

int main()
{
	freopen ("sequencequery.in","r",stdin);
	freopen ("sequencequery.out","w",stdout);
	int i,x1,x2,nrop;
	scanf("%d%d",&n,&nrop);
	
	
	for (i=1;i<=n;i++)
		scanf("%d",&vec[i]);
	build(1,1,n);
	
	for(i=1;i<=nrop;i++)
	{	scanf("%d %d ",&x1,&x2);
			nod v;
			v.l=v.r=v.o=v.s=inf;
			query(x1,x2,1,1,n,v);
			printf("%lld\n",v.o);
		
	}
	//afisare();
	return 0;
}