# include <fstream>
# include <iostream>
# define DIM 200003
# define INF 2147000000
# define max(a,b) (a>b?a:b)
using namespace std;
struct arb{
	long long s, d, t, m;
};
long long sol, s;
arb a[4*DIM];

void upd (int k, int st, int dr, int p, int v)
{
	if (st==dr)
	{
		a[k].s=a[k].d=a[k].t=a[k].m=v;
		return;
	}
	int mij=(st+dr)/2;
	if (p<=mij)
		upd(2*k, st, mij, p, v);
	else 
		upd(2*k+1, mij+1, dr, p, v);
	a[k].t=a[2*k].t+a[2*k+1].t;
	a[k].s=max(a[2*k].t+a[2*k+1].s,a[2*k].s);
	a[k].d=max(a[2*k+1].t+a[2*k].d,a[2*k+1].d);
	a[k].m=max(max(a[2*k].m,a[2*k+1].m),a[2*k].d+a[2*k+1].s);
}

void query(int k, int st, int dr, int i, int j)
{
	if (st>=i && dr<=j)
	{
		sol=max(sol,max(s+a[k].s,a[k].m));
		s=max(s+a[k].t,a[k].d);
		return;
	}
	int mij=(st+dr)/2;
	if (i<=mij)query(2*k, st, mij, i, j);
	if (j>mij)query(2*k+1, mij+1, dr, i, j);
}

int main()
{
	ifstream fin ("sequencequery.in");
	freopen("sequencequery.out", "w", stdout);
	int x, y, q, n;
	fin>>n>>q;
	for(int i=1;i<=n;++i)
	{
		fin>>x;
		upd(1, 1, n, i, x);
	}
	for(int i=1;i<=q;++i)
	{
		fin>>x>>y;
		s=0, sol=-INF;
		query(1, 1, n, x, y);
		printf("%lld\n", sol);
	}
	return 0;
}