// sequencequery2.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <algorithm>
using namespace std;

const int NMAX = 100001;
const int MMAX = 100001;
const int INF = 1000000000;
const int ARBMAX = 1 << 18;

int N, M;
int val[NMAX];
int A[ARBMAX], B[ARBMAX], C[ARBMAX], D[ARBMAX];
int x, y;
int S, rez;

void update(int nod, int st, int dr)
{
	if(st == dr)
	{
		A[nod] = B[nod] = C[nod] = val[st];
		D[nod] = val[st];
		return;
	}

	int mij = (st + dr) / 2;

	update(2 * nod, st , mij);
	update(2 * nod + 1, mij + 1, dr);

	A[nod] = max(A[2 * nod], D[2 * nod] + A[2 * nod + 1]);
	B[nod] = max(B[2 * nod] + D[2 * nod + 1], B[2 * nod + 1]);
	C[nod] = max(max(C[2 * nod], C[2 * nod + 1]), B[2 * nod] + A[2 * nod + 1]);
	D[nod] = D[2 * nod] + D[2 * nod + 1];
}

void query(int nod, int st, int dr)
{
	if(x <= st && dr <= y)
	{
		rez = max(rez, max(S + A[nod], C[nod]));
		S = max(S + D[nod], B[nod]);
		return;
	}

	int mij = (st + dr) / 2;
	if(x <= mij)
		query(2 * nod, st, mij);
	if( mij + 1 <= y)
		query(2 * nod + 1, mij + 1, dr);
}

void citire()
{
	scanf("%d%d", &N, &M);
	for(int i = 1 ; i <= N ; i++)
		scanf("%d", &val[i]);
	update(1, 1, N);
	for(int i = 1 ; i <= M ; i++)
	{
		scanf("%d %d", &x, &y);
		S = -INF, rez = -INF;
		query(1, 1, N);
		printf("%d\n", rez);
	}
}

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