#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin ("sequencequery.in");
ofstream fout("sequencequery.out");
const int inf=-1000000000000000;
struct el
{
    int maxi,pre,suf,s;
};

struct abint
{
    el v[400002];

    void update (int nod,int st,int dr,int poz,int val)
    {
        if (st==dr)
        {
            v[nod].maxi=val;
            v[nod].pre=val;
            v[nod].suf=val;
            v[nod].s=val;
            return ;
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
            update(2*nod,st,mij,poz,val);
        else
            update(2*nod+1,mij+1,dr,poz,val);
        v[nod].s=v[2*nod].s+v[2*nod+1].s;
        v[nod].pre=max(v[2*nod].pre,v[2*nod].s+v[2*nod+1].suf);
        v[nod].suf=max(v[2*nod+1].suf,v[2*nod+1].s+v[2*nod].suf);
        v[nod].maxi=max(max(v[2*nod].maxi,v[2*nod+1].maxi),v[2*nod].suf+v[2*nod+1].pre);
    }

    el  query (int nod,int st,int dr,int a,int b)
    {
        if (b<st || dr< a)
            return {inf,inf,inf,v[nod].s};
        if (a<=st && dr<= b)
            return v[nod];
        int mij=(st+dr)/2;
        if (b<=mij)
            return query(2*nod,st,mij,a,b);
        else if (a>mij)
            return query (2*nod+1,mij+1,dr,a,b);
        else
            {
                el A=query(2*nod,st,mij,a,b),B=query (2*nod+1,mij+1,dr,a,b);
                int PRE=max(A.pre,A.s+B.pre);
                int SUF=max(B.suf,B.s+A.suf);
                int M=max(max(A.maxi,B.maxi),A.suf+B.pre);
                int S=A.s+B.s;
                return {M,PRE,SUF,S};
            }
    }

} Arb;

int32_t main()
{
    int n,i,x,q,t,a,b;
    fin>>n>>q;
    for (i=1; i<=n; i++)
    {
        fin>>x;
        Arb.update(1,1,n,i,x);
    }
    for (; q>0; q--)
    {
        fin>>a>>b;
        el Y= Arb.query(1,1,n,a,b);
        fout<<Y.maxi<<'\n';
    }
    return 0;
}