#include <fstream>
using namespace std;
#define INF (1 << 30) - 1
#define DIM 100001

ifstream fi ("sequencequery.in");
ofstream fo ("sequencequery.out");

int N, Q, V[DIM], P, U, R, S;
struct arb { int S, L, R, M; } A[DIM << 2];

int Max (int a, int b, int c = -INF)
{
	a = a > b ? a : b;
	return a > c ? a : c;
}

void init (int nod, int st, int dr)
{
	if (st == dr)
	{
		A[nod].S = A[nod].L = A[nod].R = A[nod].M = V[st];
		return;
	}	
	int m = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	init (nodst, st, m);
	init (noddr, m + 1, dr);	
	
	A[nod].S = A[nodst].S + A[noddr].S;
	A[nod].L = Max (A[nodst].L, A[nodst].S + A[noddr].L);
	A[nod].R = Max (A[noddr].R, A[noddr].S + A[nodst].R);
	A[nod].M = Max (A[nodst].R + A[noddr].L, A[nodst].M, A[noddr].M);
}

void query (int nod, int st, int dr)
{
	if (P <= st && dr <= U)
	{
		R = Max (R, A[nod].M, S + A[nod].L);
		S = Max (S + A[nod].S, A[nod].R);
		return;
	}
	int m = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if (P <= m)
		query (nodst, st, m);
	if (m < U)
		query (noddr, m + 1, dr);
}

int main ()
{	
	fi >> N >> Q;
	for (int i = 1; i <= N; i++)
		fi >> V[i];
	
	init (1, 1, N);
	for (int i = 1; i <= Q; i++)
	{
		fi >> P >> U;
		R = S = -INF;
		query (1, 1, N);
		fo << R << '\n';
	}	
	return 0;
}