#include <fstream>
#define DIM 100100
#define INF -2147000000
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

long a[4*DIM], b[4*DIM], c[4*DIM], d[4*DIM];
long m, n;
long sol, ultim;

void Update(int,int,int,int,int);
void Query(int,int,int,int,int);

int main()
{
	fin >> n >> m;
	int ms;
	for (int i = 1; i <= n; ++i)
	{
		fin >> ms;
		Update(1,1,n, ms, i);
	}
	int x, y;
	for (int i = 1; i <= m; ++i)
	{
		fin >> x >> y;
		sol  =  INF;
		ultim = 0;
		
		Query(1,1,n,x,y);
		fout << sol << '\n';
	}
	fin.close();
	fout.close();
	return 0;
}

void Update(int nod, int st, int dr, int val, int poz)
{
	if (st == dr)
	{
		a[nod] = b[nod] = c[nod] = d[nod] = val;
		return;
	}
	
	int mij = (st + dr) / 2;
	if (poz <= mij) Update(2*nod, st, mij, val, poz);
	else 			Update(2*nod+1, mij + 1, dr, val, poz);
	
	d[nod] = d[2*nod] + d[2*nod+1];
	a[nod] = max(a[2*nod], d[2*nod] + a[2*nod+1]);
	b[nod] = max(b[2*nod+1], d[2*nod+1] + b[2*nod]);
	c[nod] = max(max(c[2*nod], c[2*nod+1]), a[2*nod+1] + b[2*nod]);
}

void Query(int nod, int st, int dr, int x, int y)
{
	if (st >= x && dr <= y)
	{
		sol = max(sol, max(c[nod], ultim + a[nod]));
		ultim = max(ultim + d[nod], b[nod]);
		return;
	}
	int mij = (st + dr) / 2;
	if (x <= mij) Query(2*nod, st, mij, x, y);
	if (y > mij) Query(2*nod+1, mij+1, dr, x, y);
}