#include <stdio.h>

#define nmax 2000005

#define infinit 2000000000L

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

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

int N, i, M;

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("%d%d", &N, &M);

	for (i = 1; i <= N; i++)
		scanf("%d", &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("%d%d", &x, &y);

		maxx = -infinit;
		ultt = -infinit;

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

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

	return 0;
}