#include <bits/stdc++.h>
using namespace std;
#define x1 "sequencequery.in"
#define x2 "sequencequery.out"
ifstream in(x1);
ofstream out(x2);
#define MAXN 100000 * 2
long long v[MAXN], n;
struct seq {
long long sum, max_sum, lmax_sum, rmax_sum;
} aint[MAXN];
seq add(seq l, seq r) {
seq ans;
ans.sum = l.sum + r.sum;
ans.lmax_sum = max(l.lmax_sum, l.sum + r.lmax_sum);
ans.rmax_sum = max(r.rmax_sum, r.sum + l.rmax_sum);
ans.max_sum = max(l.rmax_sum + r.lmax_sum, max(l.max_sum, r.max_sum));
return ans;
}
void build(int l, int r, int node) {
if (l == r) {
aint[node].sum = aint[node].max_sum = aint[node].lmax_sum = aint[node].rmax_sum = v[l];
return;
}
int mid, lChild, rChild;
mid = (l + r) / 2;
lChild = node + 1;
rChild = node + 2 * (mid - l + 1);
build(l, mid, lChild);
build(mid + 1, r, rChild);
aint[node] = add(aint[lChild], aint[rChild]);
}
seq ssm(int l, int r, int a, int b, int node) {
if(l == a && r == b)
return aint[node];
int mid, lChild, rChild;
mid = (l + r) / 2;
lChild = node + 1;
rChild = node + 2 * (mid - l + 1);
if(b <= mid)
return ssm(l, mid, a, b, lChild);
if(a > mid)
return ssm(mid + 1, r, a, b, rChild);
return add(ssm(l, mid, a, mid, lChild), ssm(mid + 1, r, mid + 1, b, rChild));
}
int main() {
int cer, a, b, i, q;
in >> n >> q;
for(i = 0; i < n; i++)
in >> v[i];
build(0, n, 0);
while(q--) {
in >> a >> b;
out << ssm(0, n, a - 1 , b - 1, 0).max_sum << '\n';
}
return 0;
}