#include<fstream>
#define N 100100
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int i,n,v[N],a,b,m;
long long sum[N],DR,sol,S[N<<2],D[N<<2],H[N<<2];
void us(int st,int dr,int po)
{
	if(st==dr)
	{
		S[po]=v[i];
		return;
	}
	int mij=(st+dr)>>1;
	if(i<=mij)
		us(st,mij,po<<1);
	else
		us(mij+1,dr,(po<<1)+1);
	S[po]=max(S[po<<1],sum[mij]-sum[st-1]+S[(po<<1)+1]);
}
void ud(int st,int dr,int po)
{
	if(st==dr)
	{
		D[po]=v[i];
		return;
	}
	int mij=(st+dr)>>1;
	if(i<=mij)
		ud(st,mij,po<<1);
	else
		ud(mij+1,dr,(po<<1)+1);
	D[po]=max(D[(po<<1)+1],sum[dr]-sum[mij]+D[po<<1]);
}
void up(int st,int dr,int po)
{
	if(st==dr)
	{
		H[po]=v[i];
		return;
	}
	int mij=(st+dr)>>1;
	if(i<=mij)
		up(st,mij,po<<1);
	else
		up(mij+1,dr,(po<<1)+1);
	H[po]=max(max(H[po<<1],H[(po<<1)+1]),D[po<<1]+S[(po<<1)+1]);
}
void find(int st,int dr,int po)
{
	if(st>=a&&dr<=b)
	{
		sol=max(sol,H[po]);
		if(S[po]+DR>sol)
			sol=S[po]+DR;
		DR=max(sum[dr]-sum[st-1]+DR,D[po]);
		if(DR<0)
			DR=0;
		return;
	}
	int mij=(st+dr)>>1;
	if(a<=mij)
		find(st,mij,po<<1);
	if(b>mij)
		find(mij+1,dr,(po<<1)+1);
}
int main ()
{
	f>>n>>m;
	for(i=1;i<=n;++i)
	{
		f>>v[i];
		sum[i]=sum[i-1]+v[i];
		us(1,n,1);
		ud(1,n,1);
		up(1,n,1);
	}
	for(i=1;i<=m;++i)
	{
		f>>a>>b;
		sol=(1<<30);
		sol*=sol;
		sol*=(-1);
		DR=0;
		find(1,n,1);
		g<<sol<<"\n";
	}
	return 0;
}