#include <stdio.h>
#define NMAX 100005

long long a[NMAX<<1+5000], b[NMAX<<1+5000], c[NMAX<<1++5000], sum[NMAX<<1+5000];
int n, m;
int v[NMAX];

#define mid(st, dr) (((st)+(dr)) >> 1)
#define left(n) ((n) << 1)
#define right(n) ((n) << 1) + 1
#define max(a, b) ((a) > (b)) ? (a) : (b)


void build(int n, int st, int dr)
{
	if(st == dr)
	{
		a[n] = b[n] = c[n] = v[st];
		sum[n] = v[st];
	}
	else
	{
		build(left(n), st, mid(st, dr));
		build(right(n), mid(st, dr)+1, dr);

		a[n] = max(a[left(n)], sum[left(n)] + a[right(n)]);
		b[n] = max(b[right(n)], sum[right(n)] + b[left(n)]);
		c[n] = max(max(c[left(n)], c[right(n)]),  a[right(n)]+b[left(n)]);
		sum[n] = sum[right(n)] + sum[left(n)];
	}
}

void read()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", v+i);
	}
}

long long s, ans;

void query(int n, int st, int dr, int x, int y)
{
	if(x <= st && y >= dr)
	{
		//s = max(s, 0);
		ans = max(max(ans, a[n]), max(s+a[n], c[n]));
		s = max(b[n], s+sum[n]);


	}
	else
	{
		if(x <= (mid(st, dr)))
			query(left(n), st, mid(st, dr), x, y);
		if(y > (mid(st, dr)))
			query(right(n), (mid(st, dr))+1, dr, x, y);
	}
}

int main()
{
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);

	read();

	build(1, 1, n);

	for(int x, y, i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x, &y);
		s = ans = -2000000000;
		query(1, 1, n, x, y);
		printf("%lld\n", ans);
	}

	return 0;
}