#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()
        {
        }

        inline 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];

inline void add(int nod, int left, int right, int place, int 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)));
}

inline 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);

    scanf("%d %d", &n, &m);

    for (int i = 1; i <= n; i++)
    {
        int elem;
        scanf("%d", &elem);

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

    for (; m; m--)
    {
		int limSt, limDr;
		scanf("%d %d", &limSt, &limDr);
		
		printf("%lld\n", query(1, 1, n, (limSt), (limDr)).sumSeq);
    }

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