#include<fstream>
#include<string.h>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<array>
#include<deque>
#include<math.h>
#include<unordered_set>
#include<set>
#include<iomanip>
#include<bitset>
using namespace std;
long long arb[300400], st[300400], dr[300400], sum[300400],v[100100], val, i, j, k, n, q, maxim, a, b, type, lg2, start,m,S;
ifstream f("sequencequery.in");
ofstream g("sequencequery.out");
//ifstream f("file.in");
//ofstream g("file.out");
void initADI(int nod,int lf, int rt)
{
	if (lf == rt) 
	{
		st[nod] = dr[nod] = arb[nod] = v[lf];
		sum[nod] = v[lf];
	}
	else 
	{
		int mid = (lf + rt)/2;
		initADI(nod<<1,lf, mid);
		initADI((nod<<1)+1, mid + 1, rt);
		st[nod] = max(st[nod << 1], sum[nod << 1] + st[(nod << 1) + 1]);
		dr[nod] = max(dr[nod << 1] + sum[(nod << 1) + 1], dr[(nod << 1) + 1]);
		arb[nod] = max(max(arb[nod << 1], arb[(nod << 1) + 1]), dr[nod << 1] + st[(nod << 1) + 1]);
		sum[nod] = sum[nod << 1] + sum[(nod << 1) + 1];
	}
}
void Querry(int nod, int lf, int rt,int ql,int qr)
{
	if (ql <= lf && rt <= qr)
	{
		if (S < 0)
			S = 0;
		maxim = max(maxim, max(S + st[nod], arb[nod]));
		S = max(S + sum[nod], dr[nod]);
	}
	else
	{
		if (ql <= (lf + rt) / 2)
			Querry(nod << 1, lf, (lf + rt) / 2, ql, qr);
		if (qr > (lf + rt) / 2)
			Querry((nod << 1)+1, ((lf + rt) / 2)+1,rt, ql, qr);
	}
}
int main()
{

	f >> n>>q;
	for (i=1;i<= n; i++)
	{
		f >> v[i];
	}
	initADI(1,1,n);
	for (j = 1; j <= q; j++)
	{
		f >> a >> b;
		maxim = -2000000000;
		S = 0;
		Querry(1, 1, n, a, b);
		g << maxim << "\n";
	}
	return 0;
}