#include <fstream>
#define DIM 100010
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");

int i, n, m, x, a, b;
struct sQuery{
	long long S, st, dr, Ssecv;
} v[4 * DIM], sol_global;
void update(int nod, int p, int u, int poz, int x)
{
	if(p == u)
	{
		v[nod].S = x;
		v[nod].st = x;
		v[nod].dr = x;
		v[nod].Ssecv = x;
		return;
	}
	int m = (p + u) / 2;
	if(p <= m)
		update(2 * nod, p, m, poz, x);
	else
		update(2 * nod, m + 1, u, poz, x);

	v[nod].S = v[2 * nod].S + v[2 * nod + 1].S;
	v[nod].st = max(v[2 * nod].st, v[2 * nod].S + v[2 * nod + 1].st);
	v[nod].dr = max(v[2* nod + 1].dr, v[2* nod + 1].S + v[2 * nod].dr);
	v[nod].Ssecv = max(v[2 * nod].Ssecv, max(v[2 * nod + 1].Ssecv, v[2 * nod].dr + v[2*nod + 1].st));

}
sQuery query(int nod, int p, int u, int a, int b)
{
	if(a <= p && u <= b)
	{
		return v[nod];
	}
	m = ( p + u) / 2;
	int ok_st = 0,  ok_dr = 0;
	if(a <= m){
		sQuery s_st = query(2 * nod, p, m , a, b);
		ok_st = 1;
	}
	if(m < b){
		sQuery s_dr = query(2 * nod + 1, m + 1, u, a, b);
		ok_dr = 1;
	}
	if(ok_st && ok_dr){
		sQuery sol = 0;
		sol.S = s_st.S + s_dr.S;
		sol.st = max(s_st.st, s_st.S + s_dr.st);
		sol.dr = max(s_dr.dr, s_dr.S + s_st.dr);
		sol_Ssecv = max(s_st.Ssecv, max(s_dr.Ssecv, s_st.dr + s_dr.st));
		return sol;
	}
	else
		if(ok_st)
			return s_st;
		else
			return s_dr;
}
int main()
{
    fin >> n >> m;
    for(i = 1; i <= n; i ++)
    {
    	fin >> x;
    	update(1, 1, n, i, x);
    }
    for(i = 1; i <= m; i ++)
    {
		fin >> a >> b;
		sol_global = query(1,1,n,a,b);
		fout << sol_global.Ssecv;
    }
    return 0;
}