#include <fstream>
#include <iostream>
using namespace std;
ifstream fin    ("sequencequery.in");
ofstream fout("sequencequery.out");
struct noduri
{
    long long  left,right,s,maxx;
/// left/right pt suma din st/dr, s pentru suma totala interval
/// maxx secventa cea mai buna din interval
};
noduri a[400023],x;
int 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].left=a[nod].right=a[nod].s;
        return;
    }
    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,a[2*nod+1].maxx);
    a[nod].maxx=max(a[nod].maxx , a[2*nod].right+a[2*nod+1].left);
}
noduri query(int nod,int st,int dr)
{
      bool 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
        {
            r.s=nodst.s+noddr.s;
            r.left=max(nodst.left,nodst.s+noddr.left);
            r.right=max(noddr.right,noddr.left+nodst.right);
            r.maxx=max(nodst.maxx,noddr.maxx);
            r.maxx=max(r.maxx,noddr.left+nodst.right);
            return r;
        }
    }
}
int main()
{
    fin>>n>>m;
    build(1,1,n);
    for(i=1; i<=m; i++)
    {
        fin>>a1>>b1;
        x=query(1,1,n);
        fout<<x.maxx<<"\n";
    }

}