/**
* author: zhougz
* created: 03/01/2022 10:55:06
**/
#include "bits/stdc++.h"
using namespace std;
int blk_sz;
struct query {
int l, r, idx;
bool operator<(const query &rhs) const {
return l / blk_sz != rhs.l / blk_sz ? l < rhs.l : (r < rhs.r) ^ ((l / blk_sz) & 1);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin >> n >> q;
blk_sz = n / sqrt(q);
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
vector<query> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].l--;
queries[i].r--;
queries[i].idx = i;
}
sort(queries.begin(), queries.end());
vector<int> v(arr.begin(), arr.end());
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
vector<int> idx(n);
for (int i = 0; i < n; i++) {
idx[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
}
const int N = 1 << (int)ceil(log2(v.size()));
vector<long long> t(2 * N);
auto update = [&](int x, int val) {
t[x += N] += val;
while ((x >>= 1) != 0) {
t[x] = max(t[x << 1], t[(x << 1) + 1]);
}
};
auto add = [&](int x) {
update(idx[x], arr[x]);
};
auto remove = [&](int x) {
update(idx[x], -arr[x]);
};
vector<long long> res(q);
int cur_l = 0, cur_r = -1;
for (const auto &[l, r, idx] : queries) {
while (cur_l < l) {
remove(cur_l++);
}
while (cur_l > l) {
add(--cur_l);
}
while (cur_r < r) {
add(++cur_r);
}
while (cur_r > r) {
remove(cur_r--);
}
res[idx] = t[1];
}
for (auto x : res) {
cout << x << '\n';
}
return 0;
}
