#include <iostream>
#include <fstream>

#include <algorithm>

//#include <IGO_TROLL>
const int minim = -2e9;
using namespace std;

struct nod{
    int64_t s;
    int64_t l;
    int64_t r;
    int64_t m;
};
int a [100005];
nod v [400020];
int n, m, pos, x;
int ql, qr;
void update(int st,int dr,int nod)
{
    if (st==dr)
    {
        v[nod].s=x;
        v[nod].l=x;
        v[nod].r=x;
        v[nod].m=x;
        return;
    }
    int mij=(st+dr)/2;
    if (mij<pos)
        update(mij+1,dr,2*nod+1);
    else
        update(st,mij,2*nod);
    v[nod].s = v[2*nod].s + v[2*nod+1].s;
    v[nod].l = max(v[2*nod].l, v[2*nod].s+v[2*nod+1].l);
    v[nod].r = max(v[2*nod+1].r, v[2*nod+1].s + v[2*nod].r);
    v[nod].m = max (max (v[2*nod].m, v[2*nod+1].m), v[2*nod].r + v[2*nod+1].l);

}
int64_t query (int st, int dr, int nod, int64_t &s, int64_t &l, int64_t &r, int64_t &m)
{
    int64_t ls=0, ll=0, lr=0, lm=0;
    int64_t rs=0, rl=0, rr=0, rm=0;
    bool existast=false, existadr=false;
    if (ql <=st && qr>=dr)
    {
        s=v[nod].s;
        l=v[nod].l;
        r=v[nod].r;
        m=v[nod].m;
        return m;
    }
    int mij=(st+dr)/2;
    if (ql<=mij)
    {
        query(st,mij,2*nod, ls, ll, lr, lm);
        existast = true;
    }
    if (qr>mij)
    {
        query(mij+1,dr,2*nod+1, rs, rl, rr, rm);
        existadr = true;
    }
    if(!existast)
    {
        s=rs;
        l=rl;
        r=rr;
        m=rm;
        return m;
    }
    else if (!existadr)
    {
        s=ls;
        l=ll;
        r=lr;
        m=lm;
        return m;
    }
    else
    {
    s= ls + rs;
    l= max(ll, ls+rl);
    r= max(rr, rs+lr);
    m= max(max (rm, lm), lr + rl);
    return m;
    }



}
int main()
{

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

    in>>n>>m;
    int64_t aiurea=0;
    for (int i=1;i<=n;++i)
    {
        in>>a[i];
        pos=i;
        x=a[i];
        update(1, n, 1);
    }
    while (m--)
    {
        in>>ql>>qr;
        out<<query(1, n, 1, aiurea,aiurea,aiurea,aiurea)<<"\n";


    }



}