#include<fstream>
#include<cmath>
using namespace std;
int n,m,v[100100];
int poz,val,A,B;
long long S,rez;
struct Nod{long long L,R,best,sum;};
Nod AInt[525000];

inline void Build(int nod,int st,int dr)
{
	if(st==dr)
	{
		AInt[nod].L=AInt[nod].R=AInt[nod].best=AInt[nod].sum=v[st];
		return;
	}
	int mij=(st+dr)/2,fiu=2*nod;
	Build(fiu,st,mij);
	Build(fiu+1,mij+1,dr);
	AInt[nod].L=max(AInt[fiu].L,AInt[fiu].sum+AInt[fiu+1].L);
	AInt[nod].R=max(AInt[fiu+1].R,AInt[fiu+1].sum+AInt[fiu].R);
	AInt[nod].best=max(max(AInt[fiu].best,AInt[fiu+1].best),AInt[fiu].R+AInt[fiu+1].L);
	AInt[nod].sum=AInt[fiu].sum+AInt[fiu+1].sum;
}

inline void Query(int nod,int st,int dr)
{
	if(A<=st && dr<=B)
	{
		if(S<0)
			S=0;
		rez=max(rez,max(AInt[nod].best,AInt[nod].L+S));
		S=max(AInt[nod].sum+S,AInt[nod].R);
		return;
	}
	int mij=(st+dr)/2,fiu=2*nod;
	if(A<=mij)
		Query(fiu,st,mij);
	if(mij+1<=B)
		Query(fiu+1,mij+1,dr);
}

int main()
{
	int i;
	ifstream fin("sequencequery.in");
	ofstream fout("sequencequery.out");
	fin>>n>>m;
	for(i=1;i<=n;i++)
		fin>>v[i];
	Build(1,1,n);
	for(i=1;i<=m;i++)
	{
		fin>>A>>B;
		S=0LL;
		rez=-10000000001LL;
		Query(1,1,n);
		fout<<rez<<"\n";
	}
	fin.close();
	fout.close();
	return 0;
}