#include <cstdio>
#include <cstring>

#define max(a,b) ((a)>(b)?(a):(b))

#define file_in "sequencequery.in"
#define file_out "sequencequery.out"

#define Nmax 401000
#define Inf 0x3f3f3f3f

struct sq
{
	int st,dr,sd,sum;
}a[Nmax];

int n,m,x,y,i;
long long rez,s;

void update(int nod, int ls, int ld, int poz, int val)
{
	if (ls==ld)
	{
		a[nod].st=a[nod].dr=a[nod].sd=a[nod].sum=val;
		return ;
	}
	
	int mij=(ls+ld)>>1;
	
	if (poz<=mij)
	{
		update(2*nod,ls,mij,poz,val);
	}
	else
	if (poz>mij)
	{
		update(2*nod+1,mij+1,ld,poz,val);
	}
	
	a[nod].st=max(a[2*nod].st,a[2*nod].sum+a[2*nod+1].st);
	a[nod].dr=max(a[2*nod+1].dr,a[2*nod+1].sum+a[2*nod].dr);
	a[nod].sd=max(max(a[2*nod].sd,a[2*nod+1].sd),a[2*nod].dr+a[2*nod+1].st);
	a[nod].sum=a[2*nod].sum+a[2*nod+1].sum;	
}

void query(int nod, int ls, int ld)
{
	if (x<=ls && ld<=y)
	{
		rez=max(rez,max(s+a[nod].st,a[nod].sd));
		s=max(s+a[nod].sum,a[nod].dr);
		return ;
	}
	
	int mij=(ls+ld)>>1;
	
	if (x<=mij)
	{
		query(2*nod,ls,mij);
	}
	if (mij<y)
	{
		query(2*nod+1,mij+1,ld);
	}
}
	

int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &n,&m);
	
	for (i=1;i<=n;++i)
	{
		scanf("%d", &x);
		update(1,1,n,i,x);
	}
	
	while(m--)
	{
		rez=-Inf;
		s=0;
		scanf("%d %d", &x,&y);
		query(1,1,n);
		printf("%lld\n", rez);
	}
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}