#include <fstream>
#include <climits>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
const int DIM = 100010;
int n, m, x, y, sol;
int v[DIM];
struct treeNode {
long long sum;
long long maxSumPref;
long long maxSumSuff;
long long maxSumSubseq;
} tree[4 * DIM];
treeNode updateNode(treeNode leftNode, treeNode rightNode) {
treeNode node;
node.sum = leftNode.sum + rightNode.sum;
node.maxSumPref = max(leftNode.maxSumPref, leftNode.sum + rightNode.maxSumPref);
node.maxSumSuff = max(rightNode.maxSumSuff, leftNode.maxSumSuff + rightNode.sum);
node.maxSumSubseq = max(max(leftNode.maxSumSubseq, rightNode.maxSumSubseq),
leftNode.maxSumSuff + rightNode.maxSumPref);
return node;
}
void build(int node, int left, int right) {
if (left == right) {
tree[node] = { v[left], v[left], v[left], v[left] };
} else {
int middle = (left + right) / 2;
build(2 * node, left, middle);
build(2 * node + 1, middle + 1, right);
tree[node] = updateNode(tree[2 * node], tree[2 * node + 1]);
}
}
treeNode query(int node, int left, int right, int qLeft, int qRight) {
if (qLeft <= left && right <= qRight)
return tree[node];
int middle = (left + right) / 2;
if (qRight <= middle)
return query(2 * node, left, middle, qLeft, qRight);
if (middle + 1 <= qLeft)
return query(2 * node + 1, middle + 1, right, qLeft, qRight);
treeNode leftNode = query(2 * node, left, middle, qLeft, qRight);
treeNode rightNode = query(2 * node + 1, middle + 1, right, qLeft, qRight);
return updateNode(leftNode, rightNode);
}
int main() {
fin >> n >> m;
for (int i = 1; i <= n; i++)
fin >> v[i];
build(1, 1, n);
for (int i = 1; i <= m; i++) {
fin >> x >> y;
fout << query(1, 1, n, x, y).maxSumSubseq << '\n';
}
return 0;
}