#include <bits/stdc++.h>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define int long long
int n, q;

struct Iris {
    int suma, prefix, sufix, ans;
    int getMax() {
        bool sum0 = false, pref0 = false, suf0 = false, ans0 = false;
        if(suma == 0) sum0 = true;
        if(prefix == 0) pref0 = true;
        if(sufix == 0) suf0 = true;
        if(ans == 0) ans0 = true;
        int maxim = LONG_MIN;
        if(!sum0) maxim = max(maxim, suma);
        if(!pref0) maxim = max(maxim, prefix);
        if(!suf0) maxim = max(maxim, sufix);
        if(!ans0) maxim = max(maxim, ans);
        return maxim;
    }
}aint[400010];

inline Iris combina(Iris st, Iris dr) {
    Iris ans;
    ans.suma = st.suma + dr.suma;
    ans.prefix = max(st.prefix, st.suma + dr.prefix);
    ans.sufix = max(dr.sufix, dr.suma + st.sufix);
    ans.ans = max(st.sufix + dr.prefix, max(st.ans, dr.ans));
    return ans;
}

inline Iris make_data(int val) {
    Iris aux;
    aux.suma = val;
    aux.prefix = aux.sufix = aux.ans = max(0LL, val);
    return aux;
}

inline void build(int nod, int st, int dr) {
    if(st == dr) {
        int x; fin >> x;
        aint[nod] = make_data(x);
    }
    else {
        int mid = (st + dr) / 2;
        build(2 * nod, st, mid);
        build(2 * nod + 1, mid + 1, dr);
        aint[nod] = combina(aint[2 * nod], aint[2 * nod + 1]);
    }
}

inline void update(int nod, int poz, int st, int dr, int val) {
    if(st == dr) aint[nod] = make_data(val);
    else {
        int mid = (st + dr) / 2;
        if(poz <= mid) update(2 * nod, poz, st, mid, val);
        else update(2 * nod + 1, poz, mid + 1, dr, val);
        aint[nod] = combina(aint[2 * nod], aint[2 * nod + 1]);
    }
}

inline Iris query(int nod, int st, int dr, int a, int b) {
    if(a <= st && dr <= b) return aint[nod];
    else {
        int mid = (st + dr) / 2;
        Iris v1, v2;
        v1 = v2 = make_data(0);
        if(a <= mid) v1 = query(2 * nod, st, mid, a, b);
        if(b >= mid + 1) v2 = query(2 * nod + 1, mid + 1, dr, a, b);
        return combina(v1, v2);
    }
}

signed main()
{
    fin >> n >> q;
    build(1, 1, n);
    while(q--) {
        int st, dr;
        fin >> st >> dr;
        Iris sol = query(1, 1, n, st, dr);
        fout << sol.getMax() << '\n';
    }

    return 0;
}