#include <fstream>

using namespace std;

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

#define int long long int
#define NMAX 100008

struct nod
{
    int pref,suf,suma,maxi;
};

int n,q,i,j,x,y;
int a[NMAX];
nod tree[NMAX*4];

nod update_node(nod stanga, nod dreapta)
{
    nod current;
    current.suma=stanga.suma+dreapta.suma;
    current.pref=max(stanga.pref,stanga.suma+dreapta.pref);
    current.suf=max(dreapta.suf,dreapta.suma+stanga.suf);
    current.maxi=max(stanga.suf+dreapta.pref,max(stanga.maxi,dreapta.maxi));
    return current;
}

void build (int node, int st, int dr)
{
    if (st==dr)
    {
        tree[node].maxi=tree[node].pref=tree[node].suf=tree[node].suma=a[st];
    }
    else
    {
        int mij=(st+dr)/2;
        build (node*2,st,mij);
        build (node*2+1,mij+1,dr);
        tree[node]=update_node(tree[node*2],tree[node*2+1]);
    }

}

nod query (int node, int st, int dr, int l, int r)
{
    if (l<=st && dr<=r)
    {
        return tree[node];
    }
    else
    {
        int mij=(st+dr)/2;
        if (r<=mij)
        {
            return query(node*2,st,mij,l,r);
        }
        if (l>mij)
        {
            return query(node*2+1,mij+1,dr,l,r);
        }
        nod stanga=query(node*2,st,mij,l,r),dreapta=query(node*2+1,mij+1,dr,l,r);
        return update_node(stanga,dreapta);
    }
}

signed main()
{
    fin>>n>>q;
    for (i=1; i<=n; i++)
    {
        fin>>a[i];
    }
    build (1,1,n);
    for (i=1; i<=q; i++)
    {
        fin>>x>>y;
        fout<<query(1,1,n,x,y).maxi
        <<'\n';
    }
    return 0;
}