#include <fstream>
#include <vector>
#include <algorithm>
#define inf 9000000000000000000

using namespace std;

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

const int Nmax = 100005;

struct arbore
{
    long long st;
    long long dr;
    long long mij;
    long long total;
};

vector<arbore> Arb(4 * Nmax);

long long stanga_trecut, stanga_curent;
long long dreapta_trecut, dreapta_curent;
long long total_trecut, total_curent;

void Update (int poz, int val, int nod, int st, int dr)
{
    if (st == dr)
    {
        Arb[nod].st = 1LL * val;
        Arb[nod].dr = 1LL * val;
        Arb[nod].mij = 1LL * val;
        Arb[nod].total = 1LL * val;
        return;
    }

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

    Arb[nod].st = max(Arb[nod * 2].st, Arb[nod * 2].total + Arb[nod * 2 + 1].st);
    Arb[nod].dr = max(Arb[nod * 2].dr + Arb[nod * 2 + 1].total, Arb[nod * 2 + 1].dr);
    Arb[nod].mij = max(max(Arb[nod * 2].mij, Arb[nod * 2 + 1].mij), Arb[nod * 2].dr + Arb[nod * 2 + 1].st);
    Arb[nod].total = Arb[nod * 2].total + Arb[nod * 2 + 1].total;
}

void Query (long long&maxim, int Start, int Finish, int nod, int st, int dr)
{
    if (st >= Start && dr <= Finish)
    {
        stanga_curent = max(Arb[nod].st, dreapta_trecut + Arb[nod].st);
        dreapta_curent = max(dreapta_trecut + Arb[nod].total, Arb[nod].dr);
        total_curent = total_trecut + Arb[nod].total;
        maxim = max(maxim, Arb[nod].mij);
        maxim = max(maxim, stanga_curent);
        maxim = max(maxim, dreapta_curent);
        maxim = max(maxim, total_curent);

        stanga_trecut = stanga_curent;
        dreapta_trecut = dreapta_curent;
        total_trecut = total_curent;
        return;
    }

    int mij = (st + dr) / 2;
    if (mij >= Start) Query(maxim, Start, Finish, nod * 2, st, mij);
    if (mij < Finish) Query(maxim, Start, Finish, nod * 2 + 1, mij + 1, dr);
}

int main()
{
    int n, m;

    in.sync_with_stdio(false);
    in >> n >> m;

    for (int i = 1; i <= n; i++)
    {
        int x;
        in >> x;
        Update(i, x, 1, 1, n);
    }

    for (int i = 1; i <= m; i++)
    {
        int x, y;
        long long maxim = -inf;
        in >> x >> y;
        Query(maxim, x, y, 1, 1, n);
        out << maxim << '\n';
        stanga_curent = stanga_trecut = dreapta_curent = dreapta_trecut = total_curent = total_trecut = 0;
    }

    return 0;
}