#include <fstream>
#define DIM (1<<19)
using namespace std;
ifstream fi("sequencequery.in");
ofstream fo("sequencequery.out");
long long A[DIM]/*inceput*/,B[DIM]/*sfarsit*/,C[DIM]/*tot*/,S[DIM]/*suma*/;
int X[DIM/2];
int n,m;
long long tip,a,b;
void init(int nod, int l, int r)
{
	if (l == r)
	{
		A[nod] = B[nod] = C[nod] = X[l];
		S[nod] = X[l];
	}
	else 
	{
		int mid=(l+r)/2;
		init(2*nod, l, mid);
		init(2*nod+1, mid+1, r);
		A[nod] = max(A[2*nod], S[2*nod]+A[2*nod+1]);
		B[nod] = max(B[2*nod]+S[2*nod+1], B[2*nod+1]);
		C[nod] = max(max(C[2*nod], C[2*nod+1]), B[2*nod]+A[2*nod+1]);
		
		S[nod] = S[2*nod]+S[2*nod+1];
	}
}

long long rez,s;
void query(int nod, int l, int r,int st,int dr)
{
	if (st <= l && r <= dr) {
		rez = max(rez, max(s+A[nod], C[nod]));
		s = max(s+S[nod], B[nod]);
	} else {
		int mid=(l+r)/2;
		if (st <= mid) query(2*nod,    l, mid,st,dr);
		if (dr >  mid) query(2*nod+1, mid+1,  r,st,dr);
	}
}


int main()
{
	fi>>n>>m;
	for(int i=1;i<=n;i++)
		fi>>X[i];
	init(1,1,n);
	for(int i=1;i<=m;i++)
	{
		fi>>a>>b;
		s=0,rez=-2000000000000;
		query(1,1,n,a,b);
		fo<<rez<<"\n";
	}
	fi.close();
	fo.close();
	return 0;
}