#include <fstream>

using namespace std;

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

const long long max_size = 1e5 + 1, max_aint = 4e5 + 1, INF = 1e18 + 1;

struct arb{
    long long bestsumdr, bestsumst, sum, ans;
};

long long a[max_size];
arb aint[max_aint];

arb uniune (arb x, arb y)
{
    arb rez;
    rez.bestsumst = max(x.bestsumst, x.sum + y.bestsumst);
    rez.bestsumdr = max(y.bestsumdr, y.sum + x.bestsumdr);
    rez.sum = x.sum + y.sum;
    rez.ans = max(x.ans, max(y.ans, x.bestsumdr + y.bestsumst));
    return rez;
}

void init (long long l, long long r, long long nod)
{
    if (l == r)
    {
        aint[nod] = {a[l], a[l], a[l], a[l]};
        return;
    }
    long long m = (l + r) / 2;
    init(l, m, 2 * nod);
    init(m + 1, r, 2 * nod + 1);
    aint[nod] = uniune(aint[2 * nod], aint[2 * nod + 1]);
}

arb query (long long l, long long r, long long st, long long dr, long long nod)
{
    if (st <= l && r <= dr)
    {
        return aint[nod];
    }
    long long m = (l + r) / 2;
    if (dr <= m)
    {
        return query(l, m, st, dr, 2 * nod);
    }
    if (st > m)
    {
        return query(m + 1, r, st, dr, 2 * nod + 1);
    }
    arb nodst = query(l, m, st, m, 2 * nod), noddr = query(m + 1, r, m + 1, dr, 2 * nod + 1);
    return uniune(nodst, noddr);
}

signed main ()
{
    long long n, q;
    in >> n >> q;
    for (long long i = 1; i <= n; i++)
    {
        in >> a[i];
    }
    init(1, n, 1);
    while (q--)
    {
        long long x, y;
        in >> x >> y;
        out << query(1, n, x, y, 1).ans << '\n';
    }
    in.close();
    out.close();
    return 0;
}