#include<stdio.h>
int i,j,n,m,x,y;
long long sol,s;
int v[10000];
long long a[10000],b[10000],c[10000],sum[10000];
long long maxim(long long a,long long b)
{
	if(a>b)
		return a;
	return b;
}
void build(int nod,int li,int ls)
{
	int mij=(li+ls)/2,st=nod*2,dr=st+1;
	if(li==ls)
	{
		a[i]=v[li];
		b[i]=v[li];
		c[i]=v[li];
		sum[i]=v[li];
	}
	else
	{
		build(st,li,mij);
		build(dr,mij+1,ls);

		a[nod]=maxim(a[st],sum[st]+a[dr]);
		b[nod]=maxim(b[dr],sum[dr]+b[st]);
		c[nod]=maxim(maxim(c[st],c[dr]),b[st]+a[dr]);
		sum[nod]=sum[st]+sum[dr];
	}
}
void query(int nod,int li,int ls)
{
	int mij=(li+ls)/2,st=nod*2,dr=st+1;
	if(x<=li&&y>=ls)
	{
		sol=maxim(maxim(a[nod],s+a[nod]),maxim(sol,c[nod]));
		s=maxim(b[nod],s+sum[nod]);
	}
	else
	{
	if(li<=mij)
		query(st,li,mij);
	if(ls>mij)
		query(dr,mij+1,ls);
	}
}
int main(void)
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
		scanf("%d",&v[i]);
	build(1,1,n);
	i=i;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		s=-32999;
		sol=-333444;
		query(1,1,n);
		printf("%lld",sol);
	}
	return 0;
}