#include<cstdio>
using namespace std;
int i,n,m,val,a1,b1;
long long maxi,s1,s[300002],a[300002],b[300002],c[300002];
long long max(long long a,long long b)
{
	if(a>b) return a;
	return b;
}
void update(int nod,int st,int dr,int poz,int val)
{
	if(st==dr)
	{
		s[nod]=val;
		a[nod]=val;
		b[nod]=val;
		c[nod]=val;
		return ;
	}
	int mij=(st+dr)/2;
	if(poz<=mij)
		update(nod*2,st,mij,poz,val);
	else
		update(nod*2+1,mij+1,dr,poz,val);
	s[nod]=s[nod*2]+s[nod*2+1];
	a[nod]=max(a[nod*2],s[nod*2]+a[nod*2+1]);
	b[nod]=max(b[nod*2+1],s[nod*2+1]+b[nod*2]);
	c[nod]=max(max(c[nod*2],c[nod*2+1]),a[nod*2+1]+b[nod*2]);
}
void query(int nod,int st,int dr,int x,int y)
{
	if(x<=st&&dr<=y)
	{
		maxi=max(maxi,max(c[nod],s1+a[nod]));
		s1=max(s1+s[nod],b[nod]);
	}
	else
	{
		int mij=(st+dr)/2;
		if(x<=mij)
			query(nod*2,st,mij,x,y);
		if(y>mij)
			query(nod*2+1,mij+1,dr,x,y);
	}
}
int main()
{
freopen("sequencequery.in","r",stdin);
freopen("sequencequery.out","w",stdout);
scanf("%lld",&n);
scanf("%lld",&m);
for(i=1;i<=3*n;i++)
{
	s[i]=-1000005;
	a[i]=-1000005;
	b[i]=-1000005;
	c[i]=-1000005;
}
for(i=1;i<=n;i++)
{
	scanf("%lld",&val);
	update(1,1,n,i,val);
}
//s1=ce am in dreapta care se termina unde trebuie pana acum,la query
for(i=1;i<=m;i++)
{
	scanf("%lld",&a1);
	scanf("%lld",&b1);
	maxi=-1000005;
	s1=0;
	query(1,1,n,a1,b1);
	printf("%lld\n",maxi);
}
return 0;
}