#include <fstream>
#include <algorithm>

using namespace std;

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

const int MAX_N = 100000;

struct Node {
    long long left;
    long long right;
    long long best;
    long long sum;
};
Node T[3*MAX_N];

Node join(Node u, Node v) {
    Node w;
    if(u.sum + v.left >= u.left)
        w.left = u.sum + v.left;
    else w.left = u.left;
    if(v.sum + u.right >= v.right)
        w.right = v.sum + u.right;
    else w.right = v.right;
    w.sum = u.sum + v.sum;
    w.best = max(max(u.best, v.best), u.right + v.left);
    return w;
}


void update(int x, int l, int r, int p, int v) {
    if(r - l == 1) {
        T[x] = {v, v, v, v};
        return;
    }
    if(p < (r+l)/2)
        update(2*x, l, (r+l)/2, p, v);
    else
        update(2*x+1, (r+l)/2, r, p, v);
    T[x] = join(T[2*x], T[2*x+1]);
}

Node query(int x, int l, int r, int i, int j) {
    if(i <= l && r <= j)
        return T[x];
    else if(j <= (r+l)/2)
        return query(2*x, l, (r+l)/2, i, j);
    else if(i >= (r+l)/2)
        return query(2*x+1, (r+l)/2, r, i, j);
    else
        return join(query(2*x, l, (r+l)/2, i, j), query(2*x+1, (r+l)/2, r, i, j));
}

int main() {
    int n, m, i, x, l, r;

    in >> n >> m;
    for(i = 1; i <= n; i++) {
        in >> x;
        update(1, 1, n+1, i, x);
    }

    for(i = 1; i <= m; i++) {
        in >> l >> r;
        out << query(1, 1, n+1, l, r+1).best << '\n';
    }

    return 0;
}