#include <iostream>
#include <algorithm>

#define MAX 1 << 19
#define LM 100010
#define ll long long

using namespace std;

class nodArbInt
{
    public:
        ll sumTot, sumLeft, sumRight, sumSeq;

        nodArbInt()
        {
        }

        nodArbInt(ll sumT, ll sumL, ll sumR, ll sumS)
        {
            this->sumTot = sumT, this->sumLeft = sumL;
            this->sumRight = sumR, this->sumSeq = sumS;
        }
};

int n, m;
nodArbInt arbInt[MAX];

void add(int nod, int left, int right, int place, long key)
{
    if (left == right)
    {
        arbInt[nod] = nodArbInt(key, max(-LM, key), max(-LM, key), max(-LM, key));

        return;
    }

    int median = (left + right) / 2;
    if (median >= place)
        add(nod * 2, left, median, place, key);
    else add(nod * 2 + 1, median + 1, right, place, key);

    arbInt[nod] = nodArbInt(arbInt[nod * 2].sumTot + arbInt[nod * 2 + 1].sumTot,
        max(arbInt[nod * 2].sumLeft, arbInt[nod * 2].sumTot + arbInt[nod * 2 + 1].sumLeft),
        max(arbInt[nod * 2 + 1].sumRight, arbInt[nod * 2 + 1]. sumTot + arbInt[nod * 2].sumRight),
        max(arbInt[nod * 2].sumRight + arbInt[nod * 2 + 1].sumLeft, max(arbInt[nod * 2].sumSeq, arbInt[nod * 2 + 1].sumSeq)));
}

nodArbInt query(int nod, int left, int right, int st, int fn)
{
    if (st <= left && right <= fn)
        return arbInt[nod];

    nodArbInt stanga = nodArbInt(0, -LM, -LM, -LM), dreapta = nodArbInt(0, -LM, -LM, -LM);
    int median = (left + right) / 2;
    if (median >= st)
        stanga = query(nod * 2, left, median, st, fn);
    if (median < fn)
        dreapta = query(nod * 2 + 1, median + 1, right, st, fn);

    return nodArbInt(stanga.sumTot + dreapta.sumTot,
        max(stanga.sumLeft, stanga.sumTot + dreapta.sumLeft),
        max(dreapta.sumRight, dreapta.sumTot + stanga.sumRight),
        max(stanga.sumRight + dreapta.sumLeft, max(stanga.sumSeq, dreapta.sumSeq)));
}

int main()
{
    freopen("sequencequery.in", "r", stdin);
    freopen("sequencequery.out", "w", stdout);

    cin >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        int elem;
        cin >> elem;

        add(1, 1, n, i, elem);
    }

  //  cin >> m;

    for (; m; m--)
    {
       /* int oper;
        cin >> oper;

        if (!oper)
        {
            int loc, elem;
            cin >> loc >> elem;

            add(1, 1, n, (++loc), elem);
        }
        else
        {*/
            int limSt, limDr;
            cin >> limSt >> limDr;

            cout << query(1, 1, n, (limSt), (limDr)).sumSeq << "\n";
       // }
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}