#include <fstream>
#include <limits>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int n,m,a,b,v[100010],i;
struct structnod{
	int suma,all,left,right;
};
structnod A[400010],ans;
void build(int nod,int st,int dr) {
	if (st==dr)
		A[nod].suma=A[nod].all=A[nod].left=A[nod].right=v[st];
	else {
		int mid=(st+dr)/2;
		build(2*nod,st,mid);
		build(2*nod+1,mid+1,dr);
		A[nod].suma=A[2*nod].suma+A[2*nod+1].suma;
		A[nod].left=max(A[2*nod].left,A[2*nod].suma+A[2*nod+1].left);
		A[nod].right=max(A[2*nod+1].right,A[2*nod+1].suma+A[2*nod].right);
		A[nod].all=max(A[2*nod].all,max(A[2*nod+1].all,A[2*nod].right+A[2*nod+1].left));
	}
}
structnod query(int nod,int st,int dr,int a,int b) {
	if (a<=st&&dr<=b)
		return A[nod];
	else {
		structnod stanga,dreapta;
		int okst=0,okdr=0;
		int mid=(st+dr)/2;
		if (a<=mid) {
			stanga=query(2*nod,st,mid,a,b);
			okst=1;
		}
		if (b>mid) {
			dreapta=query(2*nod+1,mid+1,dr,a,b);
			okdr=1;
		}
		if (okst==0)
			return dreapta;
		else if (okdr==0)
			return stanga;
		else {
			structnod sol;
			sol.suma=stanga.suma+dreapta.suma;
			sol.left=max(stanga.left,stanga.suma+dreapta.left);
			sol.right=max(dreapta.right,dreapta.suma+stanga.right);
			sol.all=max(stanga.right+dreapta.left,max(stanga.all,dreapta.all));
			return sol;
		}
	}
}
int main() {
	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;
		ans=query(1,1,n,a,b);
		fout<<ans.all<<"\n";
	}
	return 0;
}