#include <fstream>

#define DIM 100010

using namespace std;

struct node {
    long long s;
    long long sst;
    long long sdr;
    long long smax;
};

node Aint[4 * DIM];
int n, m, i, a, b;
long long v[DIM];

void build(int nod, int st, int dr) {
    if (st == dr) {
        Aint[nod].s = Aint[nod].sst = Aint[nod].sdr = Aint[nod].smax = v[st];
    } else {
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        Aint[nod].s = Aint[2 * nod].s + Aint[2 * nod + 1].s;
        Aint[nod].sst = max(Aint[2 * nod].sst, Aint[2 * nod].s + Aint[2 * nod + 1].sst);
        Aint[nod].sdr = max(Aint[2 * nod + 1].sdr, Aint[2 * nod].sdr + Aint[2 * nod + 1].s);
        Aint[nod].smax = max(Aint[2 * nod].smax, max(Aint[2 * nod + 1].smax, Aint[2 * nod].sdr + Aint[2 * nod + 1].sst));
    }
}

node query(int nod, int st, int dr, int a, int b) {
    node r;
    if (a <= st && dr <= b) {
        return Aint[nod];
    } else {
        int mid = (st + dr) / 2;
        node left, right;
        int okst = 0, okdr = 0;
        if (a <= mid) {
            left = query(2 * nod, st, mid, a, b);
            okst = 1;
        }
        if (b > mid) {
            right = query(2 * nod + 1, mid + 1, dr, a, b);
            okdr = 1;
        }
        if (okst == 0)
            return right;
        else if (okdr == 0)
            return left;
        else {
            r.s = left.s + right.s;
            r.sst = max(left.sst, left.s + right.sst);
            r.sdr = max(right.sdr, right.s + left.sdr);
            r.smax = max(left.sdr + right.sst, max(left.smax, right.smax));
            return r;
        }
    }
}

int main() {
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    fin >> n >> m;
    for (i = 1; i <= n; i++)
        fin >> v[i];
    build(1, 1, n);
    for (i = 1; i <= m; i++) {
        fin >> a >> b;
        node rez = query(1, 1, n, a, b);
        fout << rez.smax << "\n";
    }
    return 0;
}