#include <stdio.h>

#define nmax 1000000

long long maxim(long long x, long long y)
{
	return (x < y? y: x);
}

long long MAX[nmax], STG[nmax], DRE[nmax], VAL[nmax], V[nmax];

long long N, i, M, infinit;

long long maxx, ultt, x, y;

void cauta(int nod, int s, int d, int a, int b)
{
	if (a <= s && d <= b)
	{
		maxx = maxim(ultt + STG[nod], maxx);
		maxx = maxim(maxx, MAX[nod]);

		ultt = maxim(DRE[nod], VAL[nod] + ultt);
	}
	else
	{
		int m = (s + d) >> 1;

		if (a <= m)
			cauta(nod<<1, s, m, a, b);

		if (m < b)
			cauta(nod<<1|1, m+1, d, a, b);
	}
}

void build(int nod, int s, int d, int a, int b)
{
	if (a <= s && d <= b)
	{
		MAX[nod] = STG[nod] = DRE[nod] = VAL[nod] = V[s];
	}
	else
	{
		int m = (s + d) >> 1;

		if (a <= m)
			build(nod<<1, s, m, a, b);
		if (m < b)
			build(nod<<1|1, m+1, d, a, b);

		STG[nod] = maxim(STG[nod<<1], VAL[nod<<1] + STG[nod<<1|1]);

		DRE[nod] = maxim(DRE[nod<<1|1], VAL[nod<<1|1] + DRE[nod<<1]);

		VAL[nod] = VAL[nod<<1] + VAL[nod<<1|1];

		MAX[nod] = maxim(MAX[nod<<1], MAX[nod<<1|1]);

		MAX[nod] = maxim(MAX[nod], DRE[nod<<1] + STG[nod<<1|1]);

		MAX[nod] = maxim(MAX[nod], STG[nod]);

		MAX[nod] = maxim(MAX[nod], DRE[nod]);
	}
}

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

	scanf("%Ld%Ld", &N, &M);

	for (i = 1; i <= N; i++)
	{
		scanf("%lld", &V[i]);
		if (V[i] < 0)
			infinit += V[i];
	}

	// construiesc un arbore de intervale unde
	// max[nod] = valoarea secventei de suma maxima din intervalul nod
	// stg[nod] = valoarea secventei de suma maxima din stanga int nod
	// dre[nod] = valoarea secventei de suma maxima din dreapta in nod

	for (i = 1; i <= N; i++)
		build(1, 1, N, i, i);

	for (i = 1; i <= M; i++)
	{
		scanf("%lld%lld", &x, &y);

		maxx = infinit;
		ultt = infinit;

		cauta(1, 1, N, x, y);

		printf("%lld\n", maxx);
	}

	return 0;
}