#include <stdio.h>
#include <vector>
#define NMAX 100005
#define INF 1<<31
int n,m,A[NMAX],a,b,rez,r,val;
int B[NMAX],C[NMAX],D[NMAX],E[NMAX],sum[NMAX];
void read()
{
	scanf("%d%d",&n,&m);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d",&A[i]);
}
inline int max(int x,int y)
{
	return x>y ? x : y;
}
void cstr(int nod,int st,int dr)
{
	if (st==dr)
	{
		B[nod]=A[st]; C[nod]=A[st]; D[nod]=A[st]; E[nod]=A[st];
		return ;
	}
	int mij=(st+dr)/2;
	cstr(nod*2,st,mij);
	cstr(nod*2+1,mij+1,dr);
	B[nod]=max(B[2*nod],E[2*nod]+B[2*nod+1]);
	C[nod]=max(C[2*nod+1],E[2*nod+1]+C[2*nod]);
	D[nod]=max(max(D[2*nod],D[2*nod+1]),C[2*nod]+B[2*nod+1]);
	E[nod]=E[2*nod]+E[2*nod+1];
}
void query(int nod,int st,int dr)
{
	if (a>dr || b<st)
		return;
	if (a<=st && dr<=b)
	{
		rez=max(rez,D[nod]);
		rez=max(rez,sum[r]+B[nod]+val);
		r++;
		sum[r]=sum[r-1]+E[nod];
		val=max(val,-sum[r]+C[nod]);
		return ;
	}
	if (st==dr)
		return ;
	int mij=(st+dr)/2;
	query(2*nod,st,mij);
	query(2*nod+1,mij+1,dr);
}
void solve()
{
	int i;
	for (i=1; i<=m; i++)
	{
		scanf("%d%d",&a,&b);
		rez=-INF; r=0; val=0;
		query(1,1,n);
		printf("%d\n",rez);
	}
}
int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	read();
	cstr(1,1,n);
	solve();
	return 0;
}