#include <fstream>

using namespace std;
const int NMAX = 2e5;
using ll = long long;
const ll INF = 1e17;

ifstream cin("sequencequery.in");
ofstream cout("sequencequery.out");

int v[NMAX + 2];
struct aint_node{
    ll st, dr, sum, ans;
}aint[4 * NMAX + 2], gol = {-INF, -INF, 0, -INF};

aint_node mergee(aint_node nod1, aint_node nod2) {
    aint_node x;
    x.st = max(nod1.st, nod1.sum + nod2.st);
    x.dr = max(nod2.dr, nod2.sum + nod1.dr);
    x.sum = nod1.sum + nod2.sum;
    x.ans = max(max(nod1.ans, nod2.ans), nod1.dr + nod2.st);
    return x;
}

void build(int nod, int st, int dr) {
    if(st == dr) {
        aint[nod].st = v[st];
        aint[nod].dr = v[st];
        aint[nod].sum = v[st];
        aint[nod].ans = v[st];
        return;
    }
    int mid = (st + dr) / 2;
    build(2 * nod, st, mid);
    build(2 * nod + 1, mid + 1, dr);
    aint[nod] = mergee(aint[2 * nod], aint[2 * nod + 1]);
}

aint_node query(int nod, int st, int dr, int pos1, int pos2) {
    if(pos2 < st || dr < pos1)
        return gol;
    if(pos1 <= st && dr <= pos2)
        return aint[nod];
    int mid = (st + dr) / 2;
    return mergee(query(2 * nod, st, mid, pos1, pos2),
                  query(2 * nod + 1, mid + 1, dr, pos1, pos2));
}


int main() {
    int n, q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
        cin >> v[i];
    build(1, 1, n);
    while(q--) {
        int st, dr;
        cin >> st >> dr;
        cout << query(1, 1, n, st, dr).ans << '\n';
    }
    return 0;
}