#include <fstream>
using namespace std;

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

const int NMAX = 1e5;
const long long INF = 1e18;

struct elem{
    long long s, m, ls, rs;
} st[4 * NMAX + 5];

int v[NMAX + 5], n, m;

void Build(int node, int l, int r){
    if(l == r){

        st[node].ls = v[l];
        st[node].m = v[l];
        st[node].rs = v[l];
        st[node].s = v[l];

        return;
    }

    int m = (l + r) / 2;
    int Ls = node * 2, Rs = Ls + 1;

    Build(Ls, l, m);
    Build(Rs, m + 1, r);

    st[node].s = st[Ls].s + st[Rs].s;
    st[node].ls = max(st[Ls].ls, st[Ls].s + st[Rs].ls);
    st[node].rs = max(st[Rs].rs, st[Rs].s + st[Ls].rs);
    st[node].m = max(st[Rs].ls + st[Ls].rs, max(st[Ls].m, st[Rs].m));

}

void Query(int node, int l, int r, int ql, int qr, long long& curr_best, long long& ans){

    if(qr < l || ql > r) return;

    if(ql <= l && qr >= r){
        ans = max(ans, max(curr_best + st[node].ls, st[node].m));
        curr_best = max(curr_best + st[node].s, st[node].rs);
        return;
    }

    int m = (l + r) / 2;
    int Ls = 2 * node, Rs = Ls + 1;

    Query(Ls, l, m, ql, qr, curr_best, ans);
    Query(Rs, m + 1, r, ql, qr, curr_best, ans);

}

int main()
{
    int i, a, b;
    fin>>n>>m;

    for(i = 1; i <= n; ++i){
        fin>>v[i];
    }

    Build(1, 1, n);

    for(i = 1; i <= m; ++i){
        fin>>a>>b;

        long long ans = -INF;
        long long curr_best = -INF;

        Query(1, 1, n, a, b, curr_best, ans);
        fout<<ans<<"\n";

    }
    return 0;
}