#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream fin("sequencequery.in");
ofstream fout("sequencequery.out");
typedef long long int64;
const int MAX_N = 100100;
const int INF = 1LL << 60;
class SegmentTree {
public:
SegmentTree();
int64 query_segment(int a, int b);
void update_tree(int pos, int val);
private:
void build_tree(int node, int lo, int hi);
int64 query(int node, int lo, int hi, int a, int b);
struct SegTreeNode {
int64 minim, maxim;
int64 best;
};
vector<SegTreeNode> tree;
int64 min_prefix;
};
int N, M;
int64 v[MAX_N];
int main() {
fin >> N >> M;
for (int i = 1; i <= N; ++i) {
fin >> v[i];
v[i] += v[i - 1];
}
SegmentTree aint;
for (int i = 1, a, b; i <= M; ++i) {
fin >> a >> b;
fout << aint.query_segment(a, b) << '\n';
}
return 0;
}
SegmentTree::SegmentTree() {
tree.resize(4 * N);
build_tree(1, 1, N);
}
void SegmentTree::build_tree(int node, int lo, int hi) {
if (lo == hi) {
tree[node].minim = v[lo - 1];
tree[node].maxim = v[lo];
tree[node].best = v[lo] - v[lo - 1];
} else {
int mid = lo + (hi - lo) / 2;
int son1 = node * 2;
int son2 = son1 + 1;
build_tree(son1, lo, mid);
build_tree(son2, mid + 1, hi);
tree[node].minim = min(tree[son1].minim, tree[son2].minim);
tree[node].maxim = max(tree[son1].maxim, tree[son2].maxim);
tree[node].best = max(tree[son1].best,
max(tree[son2].best,
tree[son2].maxim - tree[son1].minim));
}
}
inline int64 SegmentTree::query_segment(int a, int b) {
min_prefix = INF;
return query(1, 1, N, a, b);
}
int64 SegmentTree::query(int node, int lo, int hi, int a, int b) {
if (a <= lo && b >= hi) {
int64 result = tree[node].best;
if (min_prefix != INF) {
result = max(result, tree[node].maxim - min_prefix);
}
min_prefix = min(min_prefix, tree[node].minim);
return result;
}
int64 result = -INF;
int son1 = node * 2;
int son2 = son1 + 1;
int mid = lo + (hi - lo) / 2;
if (a <= mid) {
result = max(result, query(son1, lo, mid, a, b));
}
if (b > mid) {
result = max(result, query(son2, mid + 1, hi, a, b));
}
return result;
}