#include <fstream>
#define DEF 100010
#define INF 1 << 29

using namespace std;

struct nod {
    long long s_st;
    long long s_dr;
    long long s;
    long long Max;
};

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

int V[DEF], n, k;

nod A[4 * DEF], sol, temp;

void build (int nod, int st, int dr) {
    if (st == dr) {
       A[nod].s_st = A[nod].s_dr = A[nod].s = A[nod].Max = V[st];
       return;
    }
    int mid = (st + dr) / 2;
    build (2 * nod, st, mid);
    build (2 * nod + 1, mid + 1, dr);

    A[nod].s = A[2 * nod].s + A[2 * nod + 1].s;
    A[nod].Max = max (A[2 * nod].s_dr + A[2 * nod + 1].s_st, max (A[2 * nod].Max, A[2 * nod + 1].Max));
    A[nod].s_st = max (A[2 * nod].s_st, A[2 * nod].s + A[2 * nod + 1].s_st);
    A[nod].s_dr = max (A[2 * nod + 1].s_dr, A[2 * nod + 1].s + A[2 * nod].s_dr);
}

void querry (int nod, int st, int dr, int & a, int & b) {
    if (st >= a and dr <= b) {
        if (sol.s == 0) {
            sol = A[nod];
            return;
        }
        temp.s = sol.s + A[nod].s;
        temp.Max = max (sol.s_dr + A[nod].s_st, max (sol.Max, A[nod].Max));
        temp.s_st = max (sol.s_st, sol.s + A[nod].s_st);
        temp.s_dr = max (A[nod].s_dr, A[nod].s + sol.s_dr);
        sol = temp;
        return;
    }
    int mid = (st + dr) / 2;
    if (a <= mid)
        querry (2 * nod, st, mid, a, b);
    if (b > mid)
        querry (2 * nod + 1, mid + 1, dr, a, b);
}

int main () {
    fin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
        fin >> V[i];
    }
    build (1, 1, n);
    for (int i = 1; i <= k; ++ i) {
        int x, y;
        fin >> x >> y;
        sol.s = sol.s_dr = sol.s_st = sol.Max = 0;
        querry (1, 1, n, x, y);
        fout << sol.Max << "\n";
    }
    return 0;
}