#include <fstream>
#include <iostream>

using namespace std;

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

const long long NMax = 1e5, oo = 1e12;

long long A[4 * NMax], B[4 * NMax], C[4 * NMax], S[4 * NMax], V[NMax + 5], N, T;
struct str{long long a, b, c, s;};

void Build(int i, int st, int dr)
{
    if(st == dr)
    {
        A[i] = B[i] = C[i] = S[i] = V[st];
        return;
    }
    int m = (st + dr) >> 1;

    Build(2 * i, st, m);
    Build(2 * i + 1, m + 1, dr);

    S[i] = S[2 * i] + S[2 * i + 1];
    A[i] = max(max(S[i], A[2 * i]), S[2 * i] + A[2 * i + 1]);
    B[i] = max(max(S[i], B[2 * i + 1]), B[2 * i] + S[2 * i + 1]);
    C[i] = max(max(max(A[i], B[i]), max(C[2 * i], C[2 * i + 1])), max(B[2 * i], max(B[2 * i] + A[2 * i + 1], A[2 * i + 1])));
}

str Querry(int i, int st, int dr, int x, int y)
{
    if(y < st || dr < x)
        return {-oo, -oo, -oo, 0};

    if(x <= st && dr <= y)
        return {A[i], B[i], C[i], S[i]};

    int m = (st + dr) >> 1;
    str L = Querry(2 * i, st, m, x, y), R = Querry(2 * i + 1, m + 1, dr, x, y), Ans;

    Ans.s = L.s + R.s;
    Ans.a = max(max(Ans.s, L.a), L.s + R.a);
    Ans.b = max(max(Ans.s, R.b), L.b + R.s);
    Ans.c = max(max(max(Ans.a, Ans.b), max(L.c, R.c)), max(L.b, max(L.b + R.a, R.a)));

    return Ans;
}

int main()
{
    fin >> N >> T;

    for(int i = 1; i <= N; i++)
        fin >> V[i];

    Build(1, 1, N);
    int a, b;

    while(T--)
    {
        fin >> a >> b;
        fout << Querry(1, 1, N, a, b).c << '\n';
    }
    fin.close();
    fout.close();

    return 0;
}