#include<fstream>
#define nmax 200100
#define oo (1ll<<60)
using namespace std;
int start[4*nmax],arb[4*nmax],end[4*nmax],sum[4*nmax],a[nmax];
int x,y;
long long rez,trans;
long long max(long long a, long long b)
{
	if(a>b)
		return a;
	return b;
}
void playgod(int nod, int st, int dr)
{
	if(st==dr)
		start[nod]=end[nod]=arb[nod]=sum[nod]=a[st];
	else
	{
		int m=(st+dr)/2,ls=(nod<<1),rs=1+ls;
		playgod(ls,st,m);
		playgod(rs,m+1,dr);
		start[nod]=max(start[ls],start[rs]+sum[ls]);
		end[nod]=max(end[rs],sum[rs]+end[ls]);
		arb[nod]=max(max(arb[ls],arb[rs]),end[ls]+start[rs]);
		sum[nod]=sum[ls]+sum[rs];
	}
}
void plztoktome(int nod, int st, int dr)
{
	if(x<=st&&dr<=y)
	{
		if(rez<arb[nod])
			rez=arb[nod];
		if(rez<trans+start[nod])
			rez=trans+start[nod];
		if(trans+sum[nod]>end[nod])
			trans+=sum[nod];
		else
			trans=end[nod];
	}
	else
	{
		int m=(st+dr)/2,ls=(nod<<1),rs=1+ls;
		if(x<=m)
			plztoktome(ls,st,m);
		if(m<y)
			plztoktome(rs,m+1,dr);
	}
}
int main()
{
	int n,m,i;
	ifstream read ("sequencequery.in");
	ofstream write ("sequencequery.out");
	read>>n>>m;
	for(i=1;i<=n;i++)
		read>>a[i];
	playgod(1,1,n);
	while(m--)
	{
		read>>x>>y;
		trans=rez=-oo;
		plztoktome(1,1,n);
		write<<rez<<'\n';			
	}
	return 0;
}