#include <iostream>
using namespace std;
const int NMAX = 1e5, INF = 1e5 + 1;

struct interval {
    long long sum, pref, suf, ssm;
};

int v[NMAX + 1];
interval aint[2 * NMAX + 1];

interval combine(interval a, interval b) {
    interval retval;
    retval.sum = a.sum + b.sum;
    retval.pref = max(a.pref, a.sum + b.pref);
    retval.suf = max(b.suf, b.sum + a.suf);
    retval.ssm = max(max(a.ssm, b.ssm), a.suf + b.pref);
    return retval;
}

void build(int l, int r, int node) {
    int mid, lson, rson;
    
    if(l == r)
        aint[node] = {v[l], v[l], v[l], v[l]};
    else {
        mid = (l + r) / 2;
        lson = node + 1;
        rson = node + 2 * (mid - l + 1);
        build(l, mid, lson);
        build(mid + 1, r, rson);
        aint[node] = combine(aint[lson], aint[rson]);
    }
}

int ql, qr;

interval query(int l, int r, int node) {
    int mid, lson, rson;

    if(qr < l || ql > r) // it's not good at all
        return {-INF, -INF, -INF, -INF};
    if(l >= ql && r <= qr) // very good
        return aint[node];
    
    mid = (l + r) / 2;
    lson = node + 1;
    rson = node + 2 * (mid - l + 1);
    interval left, right;
    left = right = {-INF, -INF, -INF, -INF};
    if(ql <= mid)
        left = query(l, mid, lson);
    if(qr > mid)
        right = query(mid + 1, r, rson);
    
    return combine(left, right);
}

int main() {
    int n, m, i;
    FILE *fin, *fout;
    fin = fopen("sequencequery.in", "r");
    fout = fopen("sequencequery.out", "w");
    fscanf(fin, "%d%d", &n, &m);
    for(i = 1; i <= n; i++)
        fscanf(fin, "%d", &v[i]);
    
    build(1, n, 1);

    for(i = 1; i <= m; i++) {
        fscanf(fin, "%d%d", &ql, &qr);
        fprintf(fout, "%lld\n", query(1, n, 1).ssm);
    }

    fclose(fin);
    fclose(fout);

    return 0;
}