#include <fstream>
using namespace std;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
int n, v[100002], t[400100], arbs[400100], arbd[400100], ts[400100],sol,s;
void update(int i, int nod, int val, int st, int dr)
{
	if(st==dr)
		t[i]=ts[i]=arbs[i]=arbd[i]=val;
	else
	{
		int mij=(st+dr)/2;
		if(nod<=mij) update(2*i,nod,val,st,mij);
		else update(2*i+1,nod,val,mij+1,dr);
		
		ts[i]=ts[2*i]+ts[2*i+1];
		arbs[i]=max(arbs[2*i],ts[2*i]+arbs[2*i+1]);
		arbd[i]=max(arbd[2*i+1],ts[2*i+1]+arbd[2*i]);
		t[i]=max(t[2*i],t[2*i+1]);
		t[i]=max(t[i],arbd[2*i]+arbs[2*i+1]);
	}
}

void query(int i, int a, int b, int st, int dr)
{
	if(a<=st && dr<=b) 
		{
			if(s<0) s=0;
			if(t[i]>sol) sol=t[i];
			if(s+arbs[i]>sol) sol=s+arbs[i];
			if(s+ts[i]>s) s+=ts[i];
			if(arbd[i]>s) s=arbd[i];
		}
	else
	{
		int mij;
		mij=(st+dr)/2;
		if(a<=mij) query(2*i,a,b,st,mij);
		if(b>mij) query(2*i+1,a,b,mij+1,dr);
	}
}
int main()
{
	int i,m,x,y;
	f>>n>>m;
	for(i=1;i<=n;i++)
	{
		f>>v[i];
		update(1,i,v[i],1,n);
	}
	for(i=1;i<=m;i++)
	{
		f>>x>>y;
		s=sol=-100001;
		query(1,x,y,1,n);
		g<<sol<<'\n';
	}
}