#include<cstdio>
#include<algorithm>
#define DIM (1 << 19)
using namespace std;

int N, M, Val, Pos;
int start, finish;

long long maxim, avem;

struct Arbore
{
    int x, y, z, t;
} arb[DIM];

void Update(int, int, int);
void Query(int, int, int);

int Maxim(int a, int b)
{
    return a >= b ? a : b;
}
int main()
    {
        int i;
        freopen("sequencequery.in","r",stdin);
        freopen("sequencequery.out","w",stdout);

        scanf("%d%d", &N, &M);

        for (i = 1; i <= N; i++)
        {
            scanf("%d", &Val);
            Pos = i;
            Update(1, 1, N);
        }

        for ( ; M; M--)
        {
            scanf("%d%d", &start, &finish);
            avem = 0, maxim = -10000000000;
            Query(1, 1, N);

            printf("%lld\n", maxim);
        }

        return 0;

    }

void Update(int nod, int left, int right)
{
    if (left == right)
    {
        arb[nod].x = arb[nod].y = arb[nod].z = Val;
        arb[nod].t = Val;
        return;
    }

    int div = (right + left)/2;

    if (Pos <= div) Update(2 * nod, left, div);
    if (div < Pos)  Update(2 * nod + 1, div + 1, right);

    arb[nod].t = arb[nod * 2].t + arb[2 * nod + 1].t;
    arb[nod].x = max(arb[2 * nod].x, arb[2 * nod].t + arb[2 * nod + 1].x);
    arb[nod].y = max(arb[2 * nod + 1].y, arb[2 * nod + 1].t + arb[nod * 2].y);
    arb[nod].z = max(max(arb[2 * nod].z, arb[2 * nod + 1].z), arb[2 * nod].y + arb[2 * nod + 1].x);
}

void Query(int nod, int left, int right)
{
    if (left > finish || right < start)
        return;
    if (left >= start && right <= finish)
    {
        maxim = max(maxim, max(1LL * arb[nod].z, 1LL * (avem + arb[nod].x)));
        avem = max(1LL*(avem + arb[nod].t), 1LL * arb[nod].y);
        return;
    }

    int div = (left+right)/2;
    if ( start <= div ) Query(2 * nod, left, div);
    if ( div < finish ) Query(2 * nod + 1, div + 1, right);
}