#include <bits/stdc++.h>
#define inf (1LL << 52)

using namespace std;

ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct node {
    long long sum;
    long long pre;
    long long suf;
    long long scm;
} a[400002];
int n, q, i, v[100002];

node updateN(node st, node dr) {
    node cur;
    cur.sum = st.sum + dr.sum;

    cur.pre = max(st.pre, st.sum + dr.pre);
    cur.suf = max(dr.suf, dr.sum + st.suf);

    cur.scm = max(st.suf + dr.pre, max(st.scm, dr.scm));

    return cur;
}

void setUp(int nod, int st, int dr) {
    if(st == dr) {
        a[nod].sum = v[st];
        a[nod].pre = v[st];
        a[nod].suf = v[st];
        a[nod].scm = v[st];
    }
    else {
        int mij = (st + dr) / 2;

        setUp(nod * 2,     st,     mij);
        setUp(nod * 2 + 1, mij + 1, dr);

        a[nod] = updateN(a[nod * 2], a[nod * 2 + 1]);
    }
}

node query(int nod, int st, int dr, int qx, int qy) {
    if(qx <= st && dr <= qy) return a[nod];
    else {
        int mij = (st + dr) / 2;

        if(qy <= mij)         return query(nod * 2,     st,      mij, qx, qy);
        if(mij + 1 <= qx)     return query(nod * 2 + 1, mij + 1, dr,  qx, qy);

        node n_st = query(nod * 2,     st,      mij, qx, qy);
        node n_dr = query(nod * 2 + 1, mij + 1, dr,  qx, qy);

        return updateN(n_st, n_dr);
    }
}

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

    setUp(1, 1, n);
    while(q--) {
        int st, dr;
        fin >> st >> dr;
        fout << query(1, 1, n, st, dr).scm << "\n";
    }

    return 0;
}