#include <fstream>

using namespace std;

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

struct nod
{
    long long sum, sumLeft, sumRight, sumMax;
}arb[262144];

int n, m;

const long long inf = 1000000000000000;

void update(int nod, int st, int dr, int poz, int val)
{
    if (st == dr)
    {
        arb[nod] = {val, val, val, val};
        return;
    }

    int mij = (st + dr) / 2;
    if (poz <= mij)
        update(nod * 2, st, mij, poz, val);
    else
        update(nod * 2 + 1, mij + 1, dr, poz, val);

    arb[nod].sum = arb[nod*2].sum + arb[nod*2+1].sum;
    arb[nod].sumMax = max(arb[nod*2].sumRight + arb[nod*2+1].sumLeft, max(arb[nod*2].sumMax, arb[nod*2+1].sumMax));
    arb[nod].sumLeft = max(arb[nod*2].sumLeft, arb[nod*2].sum + arb[nod*2+1].sumLeft);
    arb[nod].sumRight = max(arb[nod*2+1].sumRight, arb[nod*2+1].sum + arb[nod*2].sumRight);
}

void query(int nod, int st, int dr, int start, int finish, long long &sumRight, long long &s)
{
    if (start <= st && dr <= finish)
    {
        s = max(s, max(arb[nod].sumMax, sumRight + arb[nod].sumLeft));
        sumRight = max(sumRight + arb[nod].sum, arb[nod].sumRight);
        return;
    }

    int mij = (st + dr) / 2;
    if (start <= mij)
        query(nod * 2, st, mij, start, finish, sumRight, s);
    if (mij < finish)
        query(nod * 2 + 1, mij + 1, dr, start, finish, sumRight, s);
}

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

    while (m--)
    {
        int x, y;
        f >> x >> y;

        long long s = -inf, sumRight = -inf;
        query(1, 1, n, x, y, sumRight, s);
        g << s << "\n";
    }

    return 0;
}