#include <fstream>
#define nmax 100001
#define inf 1000000000

using namespace std;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");
struct sum
{
    long long tot, cs, cd, si;
};
sum res(sum a, sum b)
{
    sum aux;
    aux.tot = max(a.tot, max(b.tot, a.cd + b.cs));
    aux.cs = max(a.cs, a.si + b.cs);
    aux.cd = max(b.cd, b.si + a.cd);
    aux.si = a.si + b.si;
    return aux;
}
struct AINT
{
    sum aint[4 * nmax];
    void build(int ind, int st, int dr, int nr[])
    {
        if (st == dr)
            aint[ind] = {nr[st], nr[st], nr[st], nr[st]};
        else
        {
            build(2 * ind, st, (st + dr) / 2, nr);
            build(2 * ind + 1, (st + dr) / 2 + 1, dr, nr);
            aint[ind] = res(aint[2 * ind], aint[2 * ind + 1]);
        }
    }
    sum query(int ind, int stq, int drq, int st, int dr)
    {
        if (st >= stq && dr <= drq)
            return aint[ind];
        else
        {
            sum aux = {-inf, -inf, -inf, -inf};
            if (stq <= (st + dr) / 2)
                aux = query(2 * ind, stq, drq, st, (st + dr) / 2);
            if (drq > (st + dr) / 2)
                aux = res(aux, query(2 * ind + 1, stq, drq, (st + dr) / 2 + 1, dr));
            return aux;
        }
    }
};
int nr[nmax];
AINT v;

int main()
{
    int n, q, a, b, i;
    cin >> n >> q;
    for (i = 1; i <= n; i++)
        cin >> nr[i];
    v.build(1, 1, n, nr);
    while (q)
    {
        cin >> a >> b;
        cout << v.query(1, a, b, 1, n).tot << '\n';
        q--;
    }
    return 0;
}