#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;
    int ls = 2*nod;
    int rs = 2*nod + 1;
    if (mij<pos)
        update(mij+1,dr,rs);
    else
        update(st,mij,ls);
    v[nod].s = v[ls].s + v[rs].s;
    v[nod].l = max(v[ls].l, v[ls].s+v[rs].l);
    v[nod].r = max(v[rs].r, v[rs].s + v[ls].r);
    v[nod].m = max (max (v[ls].m, v[rs].m), v[ls].r + v[rs].l);

}
int64_t query (int st, int dr, int nod, int64_t &r, int64_t &m)
{
    bool existast=false, existadr=false;
    if (ql <=st && qr>=dr)
    {
        m= max(max(m, v[nod].m), r + v[nod].l);
        r= max(v[nod].r, r+v[nod].s);
        return;
    }
    int mij=(st+dr)/2;
    if (ql<=mij)
        query(st, mij, 2*nod, r, m);
    if (qr>mij)
        query(mij+1, dr, 2*nod+1, r, m);

}
int main()
{

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

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