#include <fstream>
#include <iostream>
using namespace std;
#define INF 999999999999999
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
struct nod {
    long long m, l, r, s;
};
nod a[500005];
int n, m;
long long sum;
void update(long long node, long long l, long long r, long long p, long long v) {
    if (l == r) {
        a[node].s = v;
        a[node].l = v;
        a[node].r = v;
        a[node].m = v;
        return;
    }
    long long ls = node * 2, rs = ls + 1;
    long long m = (l + r) / 2;
    if  (p <= m) {
        update(ls, l, m, p, v);
    }
    else
        update(rs, m + 1, r, p, v);
    a[node].s = a[ls].s + a[rs].s;
    a[node].l = max(a[ls].l, a[ls].s + a[rs].l);
    a[node].r = max(a[rs].r, a[rs].s + a[ls].r);
    a[node].m = max(a[ls].r + a[rs].l, max(a[ls].m, a[rs].m));
}
long long query(long long node, long long l, long long r, long long ql, long long qr) {
    if (ql <= l && r <= qr) {
        long long re = max(a[node].m, sum + a[node].l);
        sum = max(sum + a[node].s, a[node].r);
        return re;
    }
    long long m = (l + r) / 2;
    long long ls = node * 2, rs = ls + 1;
    long long ans = -INF;
    if (ql <= m)
        ans = max(ans, query(ls, l, m, ql, qr));
    if (qr > m)
        ans = max(ans, query(rs, m + 1, r, ql, qr));
    return ans;;
}
void readAndInit() {
    long long val;
    fin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> val;
        update(1, 1, n, i, val);
    }
}
int main()
{
    readAndInit();
    long long a, b;
    for (int i = 0; i < m; ++i) {
        sum = -INF;
        fin >> a >> b;
        fout << query(1, 1, n, a, b) << "\n";
    }
    return 0;
}