#include <bits/stdc++.h>

#define int long long

using namespace std;

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

int n, m;
int v[100100];
struct elem
{
    int ans;
    int pref;
    int suf;
    int sum;
};
elem aint[400400];

elem Merge(elem a, elem b)
{
    if(b.ans == 1e16)
        return a;
    int ans = max(max(a.ans, b.ans), a.suf + b.pref);
    int pref = max(a.pref, a.sum + b.pref);
    int suf = max(b.suf, b.sum + a.suf);
    int sum = a.sum + b.sum;
    return {ans, pref, suf, sum};
}

void update(int nod, int st, int dr, int poz, int val)
{
    if(st == dr)
    {
        aint[nod].ans = aint[nod].pref = aint[nod].suf = aint[nod].sum = val;
        return ;
    }
    int mijloc = (st + dr) / 2;
    if(poz <= mijloc)
    {
        update(2 * nod, st, mijloc, poz, val);
    }
    else
    {
        update(2 * nod + 1, mijloc + 1, dr, poz, val);
    }

    aint[nod] = Merge(aint[2 * nod], aint[2 * nod + 1]);
}

elem query(int nod, int st, int dr, int l, int r)
{
    if(st >= l && dr <= r)
    {
        return aint[nod];
    }
    if(st > r || dr < l)
    {
        int val = 1e16;
        return {val, val, val, val};
    }
    int mijloc = (st + dr) / 2;
    if(r <= mijloc)
    {
        return query(2 * nod, st, mijloc, l, r);
    }
    else
    {
        if(l >= mijloc + 1)
        {
            return query(2 * nod + 1, mijloc + 1, dr, l, r);
        }
        else
        {
            return Merge(query(2 * nod, st, mijloc, l, r),
                         query(2 * nod + 1, mijloc + 1, dr, l, r));
        }
    }
}

int32_t main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        fin >> v[i];
        update(1, 1, n, i, v[i]);
    }
    while(m--)
    {
        int l, r;
        fin >> l >> r;
        fout << query(1, 1, n, l, r).ans << '\n';
    }
}