#include <cstdio>
#include <algorithm>

#define DIM (1<<19)
using namespace std;

struct nod
{
    int sumAll;
    int lSCMax;
    int mSCMax;
    int rSCMax;
};

int N, M, X, Y;
nod ArbInt[DIM]; int Vector[DIM];

void build (int node, int start, int finish)
{
    if (start == finish)
    {
        ArbInt[node].sumAll = Vector[start];
        ArbInt[node].lSCMax = Vector[start];
        ArbInt[node].mSCMax = Vector[start];
        ArbInt[node].rSCMax = Vector[start];
    }
    else
    {
        int mid = start + ((finish - start) >> 1);

        build ((node << 1)    , start  , mid   );
        build ((node << 1) + 1, mid + 1, finish);

        ArbInt[node].sumAll = ArbInt[(node << 1)].sumAll + ArbInt[(node << 1) + 1].sumAll;
        ArbInt[node].lSCMax = max (ArbInt[(node << 1)    ].lSCMax, ArbInt[(node << 1)    ].sumAll + ArbInt[(node << 1) + 1].lSCMax);
        ArbInt[node].rSCMax = max (ArbInt[(node << 1) + 1].rSCMax, ArbInt[(node << 1) + 1].sumAll + ArbInt[(node << 1)    ].rSCMax);
        ArbInt[node].mSCMax = max ( max (ArbInt[(node << 1)].mSCMax, ArbInt[(node << 1) + 1].mSCMax), ArbInt[(node << 1)].rSCMax + ArbInt[(node << 1) + 1].lSCMax);
    }
}

nod update (int node, int start, int finish, int pos, int value)
{
    if (start == finish)
    {
        ArbInt[node].sumAll = value;
        ArbInt[node].lSCMax = value;
        ArbInt[node].mSCMax = value;
        ArbInt[node].rSCMax = value;

        return ArbInt[node];
    }
    else
    {
        int mid = start + ((finish - start) >> 1);

        if (pos <= mid)
            update ((node << 1)    , start  , mid   , pos, value);

        if (pos  > mid)
            update ((node << 1) + 1, mid + 1, finish, pos, value);

        ArbInt[node].sumAll = ArbInt[(node << 1)].sumAll + ArbInt[(node << 1) + 1].sumAll;
        ArbInt[node].lSCMax = max (ArbInt[(node << 1)    ].lSCMax, ArbInt[(node << 1)    ].sumAll + ArbInt[(node << 1) + 1].lSCMax);
        ArbInt[node].rSCMax = max (ArbInt[(node << 1) + 1].rSCMax, ArbInt[(node << 1) + 1].sumAll + ArbInt[(node << 1)    ].rSCMax);
        ArbInt[node].mSCMax = max (max (ArbInt[(node << 1)].mSCMax, ArbInt[(node << 1) + 1].mSCMax), ArbInt[(node << 1)].rSCMax + ArbInt[(node << 1) + 1].lSCMax);

        return ArbInt[node];
    }
}

nod query (int node, int start, int finish, int left, int right)
{
    if (left <= start && finish <= right)
        return ArbInt[node];
    else
    {
        int mid = start + ((finish - start) >> 1);
        nod answer1; int ok1 = 0;
        nod answer2; int ok2 = 0;
        nod answer;

        if (left <= mid)
        {
            ok1 = 1;
            answer1 = query ((node << 1)    , start  , mid   , left, right);
        }

        if (right > mid)
        {
            ok2 = 1;
            answer2 = query ((node << 1) + 1, mid + 1, finish, left, right);
        }

        if (!ok1) answer = answer2; else
        if (!ok2) answer = answer1; else
        {
            answer.sumAll = answer1.sumAll + answer2.sumAll;
            answer.lSCMax = max (answer1.lSCMax, answer1.sumAll + answer2.lSCMax);
            answer.rSCMax = max (answer2.rSCMax, answer2.sumAll + answer1.rSCMax);
            answer.mSCMax = max (max (answer1.mSCMax, answer2.mSCMax), answer1.rSCMax + answer2.lSCMax);
        }

        return answer;
    }
}

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

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

    for (int i = 1; i <= N; i ++)
    {
        scanf ("%d", &X);
        Vector[i] = X;
    }

    build (1, 1, N);

    for (int i = 1; i <= M; i ++)
    {
        scanf ("%d %d", &X, &Y);
        nod answer = query (1, 1, N, X, Y);
        printf ("%d\n", answer.mSCMax);
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}