#include <fstream>

using namespace std;

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

const int N = 1 + (1<<18);
const long long INF = (long long)1<<30;

struct nod
{
	long long st,dr,max,tot;
};

int n,m,v[N],a,b;
nod t[N];

inline int fs(int p)
{
	return p<<1;
}

inline int fd(int p)
{
	return (p<<1)+1;
}

inline long long max(long long x, long long y)
{
	return x>y ? x : y;
}

void modifica(int p, int st, int dr, int poz, long long val)
{
	if(st == dr)
	{
		t[p].st = t[p].dr = t[p].max = t[p].tot = val;
		return;
	}
	int mij = (st+dr)>>1;
	if(poz <= mij)
		modifica(fs(p), st, mij, poz, val);
	if(poz > mij)
		modifica(fd(p), mij+1, dr, poz, val);
	
	t[p].st = max(t[fs(p)].st, t[fs(p)].tot + t[fd(p)].st);
	
	t[p].dr = max(t[fd(p)].dr, t[fd(p)].tot + t[fs(p)].dr);
	
	t[p].max = max(t[fs(p)].dr + t[fd(p)].st, max(t[fs(p)].max, t[fd(p)].max));
	
	t[p].tot = t[fs(p)].tot + t[fd(p)].tot;
}

inline void init(nod &p)
{
	p.st = p.dr = p.max = p.tot = (-INF);
}

nod raspunde(int p, int st, int dr)
{
	if(a<=st && dr<=b)
		return t[p];
	int mij = (st+dr) >> 1;
	nod pc, ps, pd;
	init(ps);
	init(pd);
	if(a <= mij)
		ps = raspunde(fs(p), st, mij);
	if(b > mij)
		pd = raspunde(fd(p), mij+1, dr);
	
	pc.st = max(ps.st, ps.tot + pd.st);
	
	pc.dr = max(pd.dr, pd.tot + ps.dr);
	
	pc.max = max(ps.dr + pd.st, max(ps.max, pd.max));
	
	pc.tot = ps.tot + pd.tot;
	
	return pc;
}

int main()
{
	in>>n>>m;
	for(int i=1; i<=n; i++)
		modifica(1, 1, n, i, -INF);
	for(int i=1; i<=n; i++)
	{
		in>>v[i];
		modifica(1, 1, n, i, (long long)v[i]);
	}

	for(int i=1; i<=m; i++)
	{
		in>>a>>b;
		out<<raspunde(1, 1, n).max<<"\n";
	}
	return 0;
}