#include <cstdio>
#include <algorithm>
using namespace std;
#define lm 400000

long long S[lm], Dr[lm], St[lm], R[lm];
int n, m, p, x, a, b; 

void update (int nod, int l, int r)
{
	if (l==r)
	{
		S[nod] = Dr[nod] = St[nod] = R[nod] = x;
		return;
	}
	int m=(l+r)/2;
	if (p<=m) update (2*nod, l, m); 
	else update (2*nod+1, m+1, r);
	S[nod] = S[2*nod] + S[2*nod+1];
	Dr[nod] = max (Dr[2*nod+1], Dr[2*nod] + S[2*nod+1]);
	St[nod] = max (St[2*nod], St[2*nod+1] + S[2*nod]);
	R[nod] = max (max (max (R[2*nod], R[2*nod+1]), max (Dr[2*nod] + St[2*nod+1], S[nod])), max (Dr[nod], St[nod]));
}

struct info
{
	long long r, s, dr, st;
} v; 

void query (int nod, int l, int r)
{
	info x, y;
	if (a<=l && r<=b)
	{
		v.r = R[nod];
		v.s = S[nod];
		v.dr = Dr[nod];
		v.st = St[nod];
		return;
	}
	int m = (l+r)/2;
	x.r = x.s = x.dr = x.st = y.r = y.s = y.dr = y.st = -lm;
	if (a<=m)
	{
		query (2*nod, l, m);
		x.r = v.r;
		x.s = v.s;
		x.dr = v.dr;
		x.st = v.st;
	}
	if (m<b)
	{
		query (2*nod+1, m+1, r);
		y.r = v.r;
		y.s = v.s;
		y.dr = v.dr;
		y.st = v.st;
	}
	v.dr = max (y.dr, y.s + x.dr);
	v.st = max (x.st, x.s + y.st);
	v.s = x.s + y.s;
	v.r = max (max (max (x.r, y.r), max (v.st, v.dr)), max(v.s, x.dr + y.st));
}
	
int main()
{
	freopen("sequencequery.in","r",stdin);
	freopen("sequencequery.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i;
	for (i=1; i<=n; i++)
	{
		scanf("%d",&x);
		p=i;
		update (1, 1, n);
	}
	while (m--)
	{
		scanf("%d %d", &a, &b);
		query (1, 1, n);
		printf("%lld\n", v.r);
	}
}