#include<fstream>
#define ARBMAX 262144
#define INF 0x3f3f3f
using namespace std;
struct bla
{
	int l,r,c;
}ARB[ARBMAX];
int N,M,l,r,val,S[100001],V[100001],val_st,rez,aux;

void init(int nod,int left,int right)
{
	ARB[nod].l = ARB[nod].r = ARB[nod].c = -INF;
	if(left>=right)return;
	init(nod*2, left, (left+right)/2);
	init(nod*2+1, (left+right)/2+1, right);
}
void update(int nod,int left,int right)
{
	if(l<=left && right<=r)
	{
		ARB[nod].l = ARB[nod].r = ARB[nod].c = val;
		return;
	}
	int mid = (left+right)/2;
	
	if(l<=mid)update(nod*2, left, mid);
	else update(nod*2+1, mid+1, right);
	
	ARB[nod].c = max(ARB[nod*2].c, ARB[nod*2+1].c);
	
	ARB[nod].l = ARB[nod*2].l;
	if(S[mid] - S[left-1] + ARB[nod*2+1].l > ARB[nod].l)
		ARB[nod].l = S[mid] - S[left-1] +ARB[nod*2+1].l;
	
	ARB[nod].r = ARB[nod*2+1].r;
	if(S[right] - S[mid] + ARB[nod*2].r > ARB[nod].r)
		ARB[nod].r = S[right] - S[mid] + ARB[nod*2].r;
	
	ARB[nod].c = max(ARB[nod].c, ARB[nod*2].r + ARB[nod*2+1].l);
	ARB[nod].c = max(ARB[nod].c, max(ARB[nod].r, ARB[nod].l));
}
void querry(int nod,int left,int right)
{
	if(l<=left && right<=r)
	{
		aux =  max(ARB[nod].c, ARB[nod].l + val_st);
		val_st = max(val_st + S[right]-S[left-1], ARB[nod].r);
		if(rez<aux)
			rez=aux;
		return;
	}
	
	int mid = (left+right)/2;
	if(l<=mid)querry(nod*2,left,mid);
	if(r>mid)querry(nod*2+1,mid+1,right);
}
int main()
{
	ifstream f("sequencequery.in");
	f>>N>>M;
	int i;
	for(i=1;i<=N;++i)
	{
		f>>V[i];
		S[i] = S[i-1] + V[i];
	}
	for(i=1;i<=N;++i)
	{
		val = V[i];
		l=r=i;
		update(1,1,N);
	}
	ofstream g("sequencequery.out");
	while(M--)
	{
		f>>l>>r;
		rez = -INF;val_st = 0;
		querry(1,1,N);
		g<<rez<<"\n";
	}
	f.close();
	g.close();
	return 0;
}