#include <bits/stdc++.h>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int NMAX = 100005;
const int INF = -100000000000;
struct AINT {
long long val, l, r, s;
}aint[4 * NMAX];
void update(int x, int pos, int node, int le, int ri) {
if(le == ri)
aint[node].val = aint[node].l = aint[node].r = aint[node].s = x;
else {
int mid = (le + ri) /2;
if(pos <= mid)
update(x, pos, node * 2, le, mid);
else
update(x, pos, node * 2 + 1, mid + 1, ri);
aint[node].val = max(aint[node * 2].val, aint[node * 2 + 1].val);
aint[node].val = max(aint[node].val, aint[node * 2].r + aint[node * 2 + 1].l);
aint[node].l = aint[node * 2].l;
aint[node].l = max(aint[node].l, aint[node * 2].s + aint[node * 2 + 1].l);
aint[node].r = aint[node * 2 + 1].r;
aint[node].r = max(aint[node].r, aint[node * 2 + 1].s + aint[node * 2].r);
aint[node].s = aint[node * 2].s + aint[node * 2 + 1].s;
}
}
long long s, ans;
void query(int from, int to, int node, int le, int ri) {
if(from <= le && ri <= to) {
ans = max(ans, max(aint[node].val, aint[node].l + s));
s = max(s, max(aint[node].s + s, aint[node].r));
} else {
int mid = (le + ri) / 2;
if(from <= mid)
query(from, to, node * 2, le, mid);
if(mid < to)
query(from, to, node * 2 + 1, mid + 1, ri);
}
}
int main() {
int n, m;
in >> n >> m;
for(int i = 1; i <= n; i ++) {
int x;
in >> x;
update(x, i, 1, 1, n);
}
while(m --) {
int x, y;
in >> x >> y;
s = 0;
ans = INF;
query(x, y, 1, 1, n);
out << ans << "\n";
}
return 0;
}