#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, v[100005], x, y;
struct tr_nod
{
    ll sum;
    ll pref;
    ll suf;
    ll secsummax;
};
tr_nod aint[400055];
tr_nod update_nod(tr_nod st, tr_nod dr)
{
    tr_nod nod;
    nod.sum = st.sum + dr.sum;
    nod.pref = max(max(st.pref, st.sum + dr.pref), 0ll);
    nod.suf = max(max(dr.suf,  dr.sum + st.suf), 0ll);
    nod.secsummax = max(max(max(st.suf + dr.pref, st.secsummax), dr.secsummax), 0ll);
    return nod;
}
void build(ll nod, ll st, ll dr)
{
    if(st == dr)
    {
        aint[nod].sum =  v[st];
        aint[nod].pref = max(0ll, v[st]);
        aint[nod].suf = max(0ll, v[st]);
        aint[nod].secsummax = max(0ll, v[st]);
    }
    else
    {
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        aint[nod] = update_nod(aint[2 * nod], aint[2 * nod + 1]);
    }
}
tr_nod query(int nod, int st, int dr, int poz, ll val)
{
    if(poz <= st && dr <= val)
    {
        return aint[nod];
    }
    else
    {
        int mid = (st + dr) / 2;
        if(val <= mid)
        {
            return query(2 * nod, st, mid, poz, val);
        }
        if(mid + 1 <= poz)
        {
            return query(2 * nod + 1, mid + 1, dr, poz, val);
        }
        return update_nod(query(2 * nod, st, mid, poz, val), query(2 * nod + 1, mid + 1, dr, poz, val));
    }
}
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
int32_t main(int argc, char * argv[])
{
    fin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        fin >> v[i];
    }
    build(1, 1, n);
    while(m--)
    {
        fin >> x >> y;
        fout<< query(1, 1, n, x, y).secsummax << '\n';
    }
    return 0;
}