#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 sumaTotala, prefix, sufix, sumMax;
}aint[400010];

inline Iris combina(Iris st, Iris dr) {
    Iris rez;
    rez.sumaTotala = st.sumaTotala + dr.sumaTotala;
    rez.prefix = max(st.prefix, st.sumaTotala + dr.prefix);
    rez.sufix = max(dr.sufix, dr.sumaTotala + st.sufix);
    rez.sumMax = max(st.sufix + dr.prefix, max(st.sumMax, dr.sumMax));
    return rez;
}

inline Iris make_data(int val) {
    Iris aux;
    aux.sumaTotala = val, aux.prefix = val, aux.sufix = val, aux.sumMax = 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(LONG_MIN);
        v1.sumaTotala = v2.sumaTotala = 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.sumMax << '\n';
    }

    return 0;
}