#include <cstdio>
#include <algorithm>
#define NMAX 100023
using namespace std;
FILE *fin, *fout;
int n, m, v[NMAX], x, y;
struct interval
{
	int ans;
	int prefix;
	int sufix;
	int sum;
} arb[3*NMAX], temp;
void pun(int st, int dr, int pos, int nod)
{
	if(st == dr)
	{
		arb[nod].ans = v[pos];
		arb[nod].sum = v[pos];
		arb[nod].prefix = v[pos];
		arb[nod].sufix = v[pos];
		return ;
	}
	int mij = (st+dr)/2;
	if(pos <= mij) pun(st, mij, pos, 2*nod);
	if(pos > mij) pun(mij+1, dr, pos, 2*nod+1);
	arb[nod].ans = max(max(arb[2*nod].ans, arb[2*nod+1].ans), arb[2*nod].sufix + arb[2*nod+1].prefix);
	arb[nod].sum = arb[2*nod].sum + arb[2*nod+1].sum;
	arb[nod].prefix = max(arb[2*nod].prefix, arb[2*nod].sum + arb[2*nod+1].prefix);
	arb[nod].sufix = max(arb[2*nod].sufix + arb[2*nod+1].sum, arb[2*nod+1].sufix);
}
interval interogare(int st, int dr, int st1, int dr1, int nod)
{
	if(st == st1 && dr == dr1)
	{
		return arb[nod];
	}
	int mij = (st+dr)/2;
	if(dr1 <= mij) return interogare(st, mij, st1, dr1, 2*nod);
	if(st1 > mij) return interogare(mij+1, dr, st1, dr1, 2*nod+1);
	interval temp1, temp2, temp3;
	temp1 = interogare(st, mij, st1, mij, 2*nod);
	temp2 = interogare(mij+1, dr, mij+1, dr1, 2*nod+1);
	temp3.ans = max(max(temp1.ans, temp2.ans), temp1.sufix + temp2.prefix);
	temp3.sum = temp1.sum + temp2.sum;
	temp3.prefix = max(temp1.prefix, temp1.sum + temp2.prefix);
	temp3.sufix = max(temp1.sufix + temp2.sum, temp2.sufix);
	return temp3;
}
int main()
{
	fin = freopen("sequencequery.in", "r", stdin);
	fout = freopen("sequencequery.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i<= n; i++) scanf("%d", &v[i]);
	for(int i = 1; i<= n; i++) pun(1, n, i, 1);
	for(int i = 0; i< m; i++)
	{
		scanf("%d%d", &x, &y);
		temp = interogare(1, n, x, y, 1);
		printf("%d\n", temp.ans);
	}
	fclose(fin);
	fclose(fout);
	return 0;
}