#include <iostream>
#include <fstream>

#define ll long long

using namespace std;

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

struct Node {
    ll pref, suf, total, maxim;
};

const ll NMAX = 1e5 + 5, INF = 1e12;
Node aint[4 * NMAX];
ll n, v[NMAX];

void build(int nod, int st, int dr) {
    if (st == dr) {
        aint[nod].pref = v[st];
        aint[nod].suf = v[st];
        aint[nod].total = v[st];
        aint[nod].maxim = v[st];
        return;
    }

    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);

    int nod_st = 2 * nod, nod_dr = 2 * nod + 1;
    aint[nod].pref = max(aint[nod_st].pref, aint[nod_st].total + aint[nod_dr].pref);
    aint[nod].suf = max(aint[nod_dr].suf, aint[nod_dr].total + aint[nod_st].suf);
    aint[nod].total = aint[nod_st].total + aint[nod_dr].total;
    aint[nod].maxim = max(max(max(aint[nod].pref, aint[nod].suf), max(aint[nod_st].maxim, aint[nod_dr].maxim)), max(aint[nod].total, aint[nod_st].suf + aint[nod_dr].pref));
}

Node query(int nod, int st, int dr, int a, int b) {
    if (a <= st && dr <= b) {
        return aint[nod];
    }

    int mid = (st + dr) / 2;
    if (mid < a) {
        return query(2 * nod + 1, mid + 1, dr, a, b);
    }
    if (b <= mid) {
        return query(2 * nod, st, mid, a, b);
    }

    Node res_st = query(2 * nod, st, mid, a, b), res_dr = query(2 * nod + 1, mid + 1, dr, a, b);
    Node res;
    res.pref = max(res_st.pref, res_st.total + res_dr.pref);
    res.suf = max(res_dr.suf, res_dr.total + res_st.suf);
    res.total = res_st.total + res_dr.total;
    res.maxim = max(max(max(res.pref, res.suf), max(res_st.maxim, res_dr.maxim)), max(res.total, res_st.suf + res_dr.pref));
    return res;
}

int main() {

    int q;
    fin >> n >> q;
    for (int i = 1; i <= n; i++)
        fin >> v[i];

    build(1, 1, n);

    while (q--) {
        int a, b;
        fin >> a >> b;
        fout << query(1, 1, n, a, b).maxim << '\n';
    }

    return 0;
}