#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int SIZE = 1e5+10, INF = 10e7;

struct inter
{
    int sum, maxl, maxr, maxim;
};

int n, m, a, b;
inter arb[SIZE*4];

inter combine(inter st, inter dr)
{
    inter rez;
    rez.sum = st.sum + dr.sum;

    rez.maxl = st.maxl;
    rez.maxl = max(rez.maxl, st.sum + dr.maxl);
    rez.maxl = max(rez.maxl, st.sum);

    rez.maxr = dr.maxr;
    rez.maxr = max(rez.maxr, dr.sum + st.maxr);
    rez.maxr = max(rez.maxr, dr.sum);

    rez.maxim = max(st.maxim, dr.maxim);
    rez.maxim = max(rez.maxim, rez.maxl);
    rez.maxim = max(rez.maxim, rez.maxr);
    rez.maxim = max(rez.maxim, st.maxr + dr.maxl);
    rez.maxim = max(rez.maxim, dr.maxl);
    rez.maxim = max(rez.maxim, st.maxr);

    return rez;

}

void formArb(int ind, int st, int dr)
{
    if(st==dr)
    {
        in>>arb[ind].sum;
        arb[ind].maxim = arb[ind].maxl = arb[ind].maxr = arb[ind].sum;
        return;
    }
    int mid = (st + dr) / 2;
    formArb(ind*2, st, mid), formArb(ind*2+1, mid+1, dr);
    arb[ind] = combine(arb[ind*2], arb[ind*2+1]);
}

void coutArb(int ind, int st, int dr)
{
    cout<<ind<<": "<<st<<' '<<dr<<": ";
    cout<<arb[ind].sum<<' '<<arb[ind].maxim<<", "<<arb[ind].maxl<<" "<<arb[ind].maxr<<"\n";
    if(st>=dr) return;
    int mid = (st + dr) / 2;
    coutArb(ind*2, st, mid), coutArb(ind*2+1, mid+1, dr);
}

inter query(int ind, int st, int dr)
{
    if(a <= st && dr <= b) return arb[ind];
    int mid = (st + dr) / 2;
    inter rez1, rez2;
    rez1 = rez2 = {INF, INF, INF, INF};
    if(a<=mid) rez1 = query(ind*2, st, mid);
    if(mid<b) rez2 = query(ind*2+1, mid+1, dr);
    if(rez1.maxim == INF) return rez2;
    if(rez2.maxim == INF) return rez1;
    return combine(rez1, rez2);
}

void readit()
{
    in>>n>>m;
    formArb(1, 1, n);
}

int main()
{
    readit();
    for(int i=1; i<=m; i++)
    {
        in>>a>>b;
        out<<query(1, 1, n).maxim<<'\n';
    }
    return 0;
}