#include <fstream>

using namespace std;

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

const int NMAX = 1e5 + 1;

struct node {
    int sumaSt, sumaDr, sumaInt, sumaMax;
};

int n, m;
int v[NMAX];
node aint[4 * NMAX];
long long tempSum, ans;

void build(int nod, int st, int dr) {
    if (st == dr) {
        int val = v[st];
        aint[nod] = node{val, val, val, val};
        return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);

    aint[nod].sumaInt = aint[2 * nod].sumaInt + aint[2 * nod + 1].sumaInt;
    aint[nod].sumaSt = max(aint[2 * nod].sumaSt, aint[2 * nod].sumaInt + aint[2 * nod + 1].sumaSt);
    aint[nod].sumaDr = max(aint[2 * nod + 1].sumaDr, aint[2 * nod + 1].sumaInt + aint[2 * nod].sumaDr);
    aint[nod].sumaMax = max(max(aint[2 * nod].sumaMax, aint[2 * nod + 1].sumaMax),
                            aint[2 * nod].sumaDr + aint[2 * nod + 1].sumaSt);
}

void query(int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b) {
        ans = max(ans, max(tempSum + aint[nod].sumaSt, 1LL * aint[nod].sumaMax));
        tempSum = max(tempSum + aint[nod].sumaInt, 1LL * aint[nod].sumaDr);
        return;
    }
    int mid = (st + dr) / 2;
    if (a <= mid)
        query(2 * nod, st, mid, a, b);
    if (b > mid)
        query(2 * nod + 1, mid + 1, dr, a, b);
}

inline void read() {
    fin >> n >> m;
    for (int i = 1; i <= n; ++i)
        fin >> v[i];
    build(1, 1, n);
}

inline void solve() {
    int x, y;
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y;
        tempSum = ans = -2e9;
        query(1, 1, n, x, y);
        fout << ans << '\n';
    }
}

int main()
{
    read();
    solve();

    fin.close();
    fout.close();
    return 0;
}