#include <fstream>
 
using namespace std;
 
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
 
struct nod
{
    long long sum,left,right,smax;
}
arb[800005];
 
int n, m;
 
const long long inf =999999999999999 ;
 
void update(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        arb[nod] = {val, val, val, val};
        return;
    }
 
    int mij = (st + dr) / 2;
    if (poz <= mij)
        update(nod * 2, st, mij, poz, val);
    else
        update(nod * 2 + 1, mij + 1, dr, poz, val);
 
    arb[nod].sum = arb[nod*2].sum + arb[nod*2+1].sum;
    arb[nod].smax = max(arb[nod*2].right + arb[nod*2+1].left, max(arb[nod*2].smax, arb[nod*2+1].smax));
    arb[nod].left = max(arb[nod*2].left, arb[nod*2].sum + arb[nod*2+1].left);
    arb[nod].right = max(arb[nod*2+1].right, arb[nod*2+1].sum + arb[nod*2].right);
}
 
void query(int nod, int st, int dr, int pos1, int pos2, long long &sum, long long &s)
{
    if (pos1<=st && dr<=pos2)
    {
	//	if(s<0) s=0;
        s = max(s, max(arb[nod].smax, sum + arb[nod].left));
        sum = max(sum+ arb[nod].sum, arb[nod].right);
        return;
    }
 
    int mij = (st + dr) / 2;
    if (pos1<=mij)
        query(nod * 2, st, mij, pos1, pos2, sum, s);
    if (mij<pos2)
        query(nod * 2 + 1, mij + 1, dr, pos1,pos2, sum, s);
}
 
int main()
{
    in>>n;
 	in>>m;
    for (int i=1; i<=n; i++)
    {
        int x; 
		in>>x;
        update(1, 1, n, i, x);
    }
    for(int i=1;i<=m;i++)
    {
	//	int cerinta;
        int a,b;
        in>>a>>b;
        long long s = -inf, ans = -inf;
		   query(1, 1, n, a, b, ans, s);
       	out<<s<< "\n";
    }
    return 0;
}