#include <cstdio>
#include <cassert>
#define MAX_N 100001
struct sequence {
long long sum, sub_max_sum, left_max_sum, right_max_sum;
};
const long long INF = 2000000000;
int n, m;
int v[MAX_N];
sequence aint[MAX_N * 4];
long long ans, sum;
void read() {
assert(scanf("%d%d", &n, &m) == 2);
for (int i = 1; i <= n; ++i)
assert(scanf("%d", &v[i]) == 1);
}
long long max(long long x, long long y) {
return (x > y) ? x : y;
}
void build(int node, int left, int right) {
if (left == right) {
aint[node].sum = aint[node].sub_max_sum = aint[node].left_max_sum = aint[node].right_max_sum = v[left];
return;
}
int mid = (left + right) >> 1;
int left_son = (node << 1);
int right_son = (node << 1) + 1;
build(left_son, left, mid);
build(right_son, mid + 1, right);
aint[node].sum = aint[left_son].sum + aint[right_son].sum;
aint[node].left_max_sum = max(aint[left_son].left_max_sum, aint[left_son].sum + aint[right_son].left_max_sum);
aint[node].right_max_sum = max(aint[right_son].right_max_sum, aint[right_son].sum + aint[left_son].right_max_sum);
aint[node].sub_max_sum = max(aint[left_son].sub_max_sum, aint[right_son].sub_max_sum);
aint[node].sub_max_sum = max(aint[node].sub_max_sum, aint[left_son].right_max_sum + aint[right_son].left_max_sum);
}
void query(int node, int left, int right, int a, int b) {
if (a <= left && right <= b) {
ans = max(ans, max(aint[node].sub_max_sum, aint[node].left_max_sum + sum));
sum = max(sum + aint[node].sum, aint[node].right_max_sum);
}
int mid = (left + right) >> 1;
int left_son = (node << 1);
int right_son = (node << 1) + 1;
if (a <= mid)
query(left_son, left, mid, a, b);
if (b > mid)
query(right_son, mid + 1, right, a, b);
}
int main() {
assert(freopen("sequencequery.in", "r", stdin));
assert(freopen("sequencequery.out", "w", stdout));
read();
build(1, 1, n);
while (m) {
int a, b;
assert(scanf("%d%d", &a, &b) == 2);
sum = 0;
ans = -INF;
query(1, 1, n, a, b);
--m;
}
}