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