#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 1e5;
const long long INF = 1e18;

struct ST {
    long long s, l, r, m;
} st[N_MAX * 4 + 5];

int n, m;
int v[N_MAX + 5];

long long dp, solution;

void build(int node, int l, int r) {
    if (l == r) {
        st[node].s = v[l];
        st[node].l = v[l];
        st[node].r = v[l];
        st[node].m = v[l];

        return;
    }

    int m = (l + r) / 2;
    int ls = 2 * node, lr = ls + 1;

    build(ls, l, m);
    build(lr, m + 1, r);

    st[node].s = st[ls].s + st[lr].s;
    st[node].l = max(st[ls].l, st[ls].s + st[lr].l);
    st[node].r = max(st[lr].r, st[ls].r + st[lr].s);
    st[node].m = max(max(st[ls].m, st[lr].m), st[ls].r + st[lr].l);
}

void query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) {
        return;
    }

    if (l >= ql && qr >= r) {
        solution = max(solution, max(st[node].m, dp + st[node].l));
        dp = max(dp + st[node].s, st[node].r);

        return;
    }

    int m = (l + r) / 2;
    int ls = 2 * node, lr = ls + 1;

    query(ls, l, m, ql, qr);
    query(lr, m + 1, r, ql, qr);
}

int main() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }

    build(1, 1, n);

    while (m--) {
        int start, last;
        fin >> start >> last;

        dp = - INF, solution = -INF;
        query(1, 1, n, start, last);

        fout << solution << '\n';
    }

    fin.close();
    fout.close();

    return 0;
}