#include <iostream>
#include <fstream>
using namespace std;
ifstream in("sequencequery.in");
ofstream out("sequencequery.out");
const int INF = 1e9;
const int N = 1e5;
typedef long long ll;
ll l[4 * N], r[4 * N], sum[4 * N], best[4 * N];
void update(int node, int left, int right, int pos, int val) {
if (left > right)
return;
if (left == right) {
best[node] = val;
l[node] = val;
r[node] = val;
sum[node] = val;
return;
}
int mid = (left + right) / 2;
int leftNode = node * 2, rightNode = node * 2 + 1;
if (pos <= mid)
update(leftNode, left, mid, pos, val);
else
update(rightNode, mid + 1, right, pos, val);
l[node] = max(l[leftNode], sum[leftNode] + l[rightNode]);
r[node] = max(r[rightNode], sum[rightNode] + r[leftNode]);
sum[node] = sum[leftNode] + sum[rightNode];
best[node] = max(best[leftNode], max(best[rightNode], r[leftNode] + l[rightNode]));
}
ll ans, bestInterval;
void query(int node, int left, int right, int ql, int qr) {
if (left > right)
return;
if (ql <= left && right <= qr) {
// cout << left << ' ' << right << ":\n";
// cout << l[node] << ' ' << r[node] << '\n';
ans = max(ans, max(bestInterval + l[node], best[node]));
bestInterval = max(bestInterval + sum[node], r[node]);
// cout << ans << ' ' << bestInterval << "\n\n\n";
return;
}
int mid = (left + right) / 2;
int leftNode = node * 2, rightNode = node * 2 + 1;
if (ql <= mid)
query(leftNode, left, mid, ql, qr);
if (mid < qr)
query(rightNode, mid + 1, right, ql, qr);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
in >> n >> m;
for (int i = 1; i <= n; i++) {
int x;
in >> x;
update(1, 1, n, i, x);
}
for (int i = 1; i <= m; i++) {
int ql, qr;
in >> ql >> qr;
ans = -INF;
bestInterval = 0;
query(1, 1, n, ql, qr);
out << ans << '\n';
}
return 0;
}