#include <fstream>
using namespace std;

const int N=100002,inf=1<<30;
struct node{int S,D,C,sum;} v[3*N],sol;
int n;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");

inline void nod(node &A,node B,node C)
{
	A.S=max(B.S,B.sum+C.S);
	A.D=max(C.D,C.sum+B.D);
	A.sum=B.sum+C.sum;
	A.C=max(max(B.C,C.C),max(B.D+C.S,A.sum));
}
	

inline void update(int poz,int st,int dr,int x,int val)
{
	if (st==dr)
	{
		v[poz].S=v[poz].D=v[poz].C=v[poz].sum=val;
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	if (x<=m)
		update(S,st,m,x,val);
	else
		update(D,m+1,dr,x,val);
	nod(v[poz],v[S],v[D]);
}

inline void query(int poz,int st,int dr,int x,int y)
{
	if (x<=st && y>=dr)
	{
		nod(sol,sol,v[poz]);
		return;
	}
	int m=(st+dr)>>1,S=poz<<1,D=S+1;
	if (x<=m)
		query(S,st,m,x,y);
	if (y>m)
		query(D,m+1,dr,x,y);
}

int main()
{
	int i,x,y,t;
	in>>n>>t;
	for (i=1;i<=n;i++)
	{
		in>>x;
		update(1,1,n,i,x);
	}
	while (t--)
	{
		sol.S=sol.D=sol.C=sol.sum=-inf;
		in>>x>>y;
		query(1,1,n,x,y);
		out<<sol.C<<"\n";
	}
	return 0;
}