#include <fstream>

using namespace std;

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

constexpr int NMAX = 1e5 + 5;
constexpr int INF = 1e9 + 5;

struct arbore
{
    int sum;
    int dr;
    int st;
    int rez;
};

arbore aint[NMAX*4];

int n, m;

int a[NMAX];

void combin (arbore &a, arbore b, arbore c)
{
    a.sum = b.sum + c.sum;
    a.st = max(a.sum, max(b.st, b.sum + c.st));
    a.dr = max(a.sum, max(c.dr, c.sum + b.dr));
    a.rez = max(max(max(a.sum, max(a.st, a.dr)), max(b.rez, c.rez)), max(b.dr+c.st, max(b.dr, c.st)));
}

void update (int nod, int a, int b, int poz, int val)
{
    if (a==b)
    {
        aint[nod]={val, val, val, val};
        return;
    }
    int mij=(a+b)/2;

    if (poz <= mij) update(2*nod, a, mij, poz, val);
    else update(2*nod+1, mij+1, b, poz, val);

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

arbore query (int nod, int a, int b, int qa, int qb)
{
    if (qa <= a && b <= qb) return aint[nod];

    int mij=(a+b)/2;

    arbore nr_1={0, -INF, -INF, -INF};
    arbore nr_2={0, -INF, -INF, -INF};
    arbore aux={0, -INF, -INF, -INF};

    if (qa <= mij) nr_1=query(2*nod, a, mij, qa, qb);
    if (mij < qb) nr_2=query(2*nod+1, mij+1, b, qa, qb);

    combin(aux, nr_1, nr_2);

    return aux;
}

int main()
{
    f>>n>>m;

    for (int i=1; i<=n; ++i)
    {
        int x;
        f>>x;
        update(1, 1, n, i, x);
    }

    for (int i=1; i<=m; ++i)
    {
        int x, y;
        f>>x>>y;
        g<<query(1, 1, n, x, y).rez << '\n';
    }
    return 0;
}