#include <fstream>

using namespace std;

const int MAX_N = 1e5;
int a[MAX_N + 1];
int n, q;

struct ST {
    int sum;
    int prefMax;
    int sufMax;
    int subSumMax;
};

ST operator + (const ST &lson, const ST &rson) {
    ST answer;
    answer.sum = lson.sum + rson.sum;
    answer.prefMax = max(lson.prefMax, lson.sum + rson.prefMax);
    answer.sufMax = max(rson.sufMax, rson.sum + lson.sufMax);
    answer.subSumMax = max(lson.subSumMax, rson.subSumMax);
    answer.subSumMax = max(answer.subSumMax, lson.sufMax + rson.prefMax);
    answer.subSumMax = max(answer.subSumMax, max(lson.sufMax, rson.prefMax));
    return answer;
}

ST aint[4 * MAX_N + 1];

void build(int v, int l, int r) {
    if (l == r) {
        aint[v] = ST {a[l], a[l], a[l], a[l]};
    } else {
        int mid = (l + r) / 2;
        build(2 * v, l, mid);
        build(2 * v + 1, mid + 1, r);
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

void update(int v, int l, int r, int pos, int val) {
    if (l == r) {
        aint[v].sum = val;
        aint[v].prefMax = val;
        aint[v].sufMax = val;
        aint[v].subSumMax = val;
    } else {
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2 * v, l, mid, pos, val);
        } else {
            update(2 * v + 1, mid + 1, r, pos, val);
        }
        aint[v] = aint[2 * v] + aint[2 * v + 1];
    }
}

ST query(int v, int l, int r, int p, int q) {
    if (p <= l && r <= q) {
        return aint[v];
    } else {
        int mid = (l + r) / 2;
        if (p <= mid && mid + 1 <= q) {
            ST lq = query(2 * v, l, mid, p, q);
            ST rq = query(2 * v + 1, mid + 1, r, p, q);
            return lq + rq;
        } else if (p <= mid) {
            return query(2 * v, l, mid, p, q);
        } else if (mid + 1 <= q) {
            return query(2 * v + 1, mid + 1, r, p, q);
        }
    }
}

int main() {
    ifstream fin("sequencequery.in");
    ofstream fout("sequencequery.out");
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= q; i++) {
        int l, r;
        fin >> l >> r;
        fout << query(1, 1, n, l, r).subSumMax << "\n";
    }
    return 0;
}