#include <iostream>
#include <fstream>
#define Nmax 100005
#define inf 1000000000000
using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
long long sl[4 * Nmax], sr[4 * Nmax], sm[4 * Nmax], arbs[4 * Nmax], n, m, x, a, b, smax, st;
void upd(int nod, int l, int r, int poz, int val)
{
    int mij = (l + r) /2;
    if(l == r)
    {
        arbs[nod] = sl[nod] = sr[nod] = sm[nod] = val;
        return;
    }
    if(poz <= mij)
        upd(2 * nod, l, mij, poz, val);
    else upd(2 * nod + 1, mij + 1, r, poz, val);
    sm[nod] = max(max(sm[2 * nod], sm[2 * nod + 1]), sr[2 * nod] + sl[2 * nod + 1]);
    sl[nod] = max(sl[2 * nod], arbs[2 * nod] + sl[2 * nod + 1]);
    sr[nod] = max(sr[2 * nod + 1], arbs[2 * nod + 1] + sr[2 * nod]);
    arbs[nod] = arbs[2 * nod] + arbs[2 * nod + 1];
}
void query(int nod, int L, int R, int l, int r)
{
    int mij = (L + R) / 2;
    if(L > r || R < l)return;
    if(l <= L && R <= r)
    {
        smax = max(smax , max(sm[nod], st + sl[nod]));
        st = max(st + arbs[nod], sr[nod]);
        return;
    }
    query(2 * nod, L, mij, l , r);
    query(2 * nod + 1, mij + 1, R, l, r);
}
int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        fin >> x;
        upd(1, 1, n, i, x);
    }
  for(int i = 1; i <= m; i++)
    {
        fin >> a >> b;
        smax = -inf;
        st = 0;
        query(1, 1, n, a, b);
        fout << smax << '\n';
    }

    return 0;
}