#include <stdio.h>
#define NMAX (1<<17)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)
int n, m;
int v[NMAX];
long long A[NMAX<<1], B[NMAX<<1], C[NMAX<<1], Sum[NMAX<<1];
void build(int n, int l, int r)
{
	if (l == r) 
	{
		A[n] = B[n] = C[n] = max(v[l], 0);
		Sum[n] = v[l];
	} 
	else 
	{
		build(lf, l, md);
		build(rt, md+1, r);
		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		Sum[n] = Sum[lf]+Sum[rt];
	}
}

int p, x;

void update(int n, int l, int r) 
{
	if (l == r) 
	{
		A[n] = B[n] = C[n] = max(x,0);
		Sum[n] = x;
	} 
	else 
	{
		if (p <= md) 
			update(lf,l,md);
		else         
			update(rt,md+1,r);
		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		Sum[n] = Sum[lf]+Sum[rt];		
	}
}
int a, b;
long long ans, S;
void query(int n, int l, int r) 
{
	if (a <= l && r <= b) 
	{
		if (S < 0) 
			S = 0;
		ans = max(ans, max(S+A[n], C[n]));
		S = max(S+Sum[n], B[n]);
	} 
	else 
	{
		if (a <= md) 
			query(lf, l, md);
		if (b >  md) 
			query(rt, md+1, r);
	}
}

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", &v[i]);
	build(1, 1, n);
	while (m--) 
	{
		scanf("%d%d", &a, &b);
		S = ans = 0;
		query(1, 1, n);
		if (a==b)
			printf("%d\n",v[a]);
		else
			printf("%lld\n", ans);
	}
	return 0;
}