#include <fstream>
#include <iostream>
using namespace std;
ifstream fin    ("sequencequery.in");
ofstream fout("sequencequery.out");
struct noduri
{
    long long  left;
    long long right;
    long long s;
    long long maxx;
/// left/right pt suma din st/dr, s pentru suma totala interval
/// maxx secventa cea mai buna din interval
};
noduri a[400023],x;
long long a1,b1,n,m,i;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        fin>>a[nod].s;
        a[nod].maxx=a[nod].s;
        a[nod].left=a[nod].s;
        a[nod].right=a[nod].s;
        return;
    }
else {
		int mid=(st+dr)/2;
		build(2*nod,st,mid);
		build(2*nod+1,mid+1,dr);
		a[nod].s=a[2*nod].s+a[2*nod+1].s;
		a[nod].left=max(a[2*nod].left,a[2*nod].s+a[2*nod+1].left);
		a[nod].right=max(a[2*nod+1].right,a[2*nod+1].s+a[2*nod].right);
		a[nod].maxx=max(a[2*nod].maxx,max(a[2*nod+1].maxx,a[2*nod].right+a[2*nod+1].left));
	}
}
noduri query(int nod,int st,int dr)
{
      int okst=0,okdr=0;
     noduri nodst,noddr,r;
     if(a1<=st&&dr<=b1)
    {
        return a[nod];
    }
    else
    {

        int mid=(st+dr)/2;

        if(a1<=mid)
        {
            nodst=query(2*nod,st,mid);
            okst=1;
        }
        if(b1>mid)
        {
            noddr=query(2*nod+1,mid+1,dr);
            okdr=1;
        }
        if(okst==0)
            return noddr;
        else if(okdr==0)
            return nodst;
        else
        {
          noduri sol;
			sol.s=nodst.s+noddr.s;
			sol.left=max(nodst.left,nodst.s+noddr.left);
			sol.right=max(noddr.right,noddr.s+nodst.right);
			sol.maxx=max(nodst.right+noddr.left,max(nodst.maxx,noddr.maxx));
            return sol;
        }
    }
}
int main()
{
    fin>>n>>m;
    build(1,1,n);
    for(i=1; i<=m; i++)
    {
        fin>>a1>>b1;
        fout<<query(1,1,n).maxx<<"\n";
    }

}