#include <bits/stdc++.h>

using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
#define int long long
const int DIM = 1e5;
int n;

struct Iris {
    int sum, prefix, sufix, sumMax;
}aint[4 * DIM + 3];

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

inline void build(int nod, int st, int dr) {
    if(st == dr) {
        int x; fin >> x;
        aint[nod] = {x, x, x, 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 Iris query(int nod, int st, int dr, int a, int b) {
    if(a <= st && dr <= b) return aint[nod];
    else if(a > dr || b < st) return {0, -1000000, -1000000, -1000000};
    else {
        int mid = (st + dr) / 2;
        return combina(query(2 * nod, st, mid, a, b), query(2 * nod + 1, mid + 1, dr, a, b));
    }
}

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

    return 0;
}