#include <cstdio>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in ("sequencequery.in");

typedef long long I64;

const I64 oo=1<<20;
struct arb
{
	I64 a,b,c,d;
}adi[400001];
int n,q;
I64 sol,r;

void up (int nod,int ft,int bk,int ind,int val)
{
	if(ft==bk)
	{
		adi[nod].a=adi[nod].b=adi[nod].c=adi[nod].d=val;
		return;
	}
	int mid=(ft+bk)>>1;
	if(ind<=mid)
		up(nod<<1,ft,mid,ind,val);
	else
		up((nod<<1)+1,mid+1,bk,ind,val);
	adi[nod].a=adi[nod<<1].a+adi[(nod<<1)+1].a;
	adi[nod].b=max(adi[nod<<1].a+adi[(nod<<1)+1].b,adi[nod<<1].b);
	adi[nod].c=max(adi[(nod<<1)+1].a+adi[nod<<1].c,adi[(nod<<1)+1].c);
	adi[nod].d=max(max(adi[nod<<1].d,adi[(nod<<1)+1].d),adi[nod<<1].c+adi[(nod<<1)+1].b);
}

void read ()
{
	in>>n>>q;
	for(int x,i=1;i<=n;++i)
	{
		in>>x;
		up(1,1,n,i,x);
	}
}

void query (int nod,int ft,int bk,int st,int dr)
{
	if(ft>=st&&bk<=dr)
	{
		sol=max(sol,max(r+adi[nod].b,adi[nod].d));
		r=max(r+adi[nod].a,adi[nod].c);
		return;
	}
	int mid=(ft+bk)>>1;
	if(st<=mid)
		query(nod<<1,ft,mid,st,dr);
	if(mid<dr)
		query((nod<<1)+1,mid+1,bk,st,dr);
}

void solve ()
{
	freopen ("sequencequery.out","w",stdout);
	for(int x,y;q;--q)
	{
		in>>x>>y;
		r=0;
		sol=-oo;
		query(1,1,n,x,y);
		printf("%lld\n",sol);
	}
}

int main ()
{
	read ();
	solve ();
	return 0;
}