#include <bits/stdc++.h>
#define fastio \
ios_base::sync_with_stdio(0); \
cin.tie(0);
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vp vector<pi>
#define vpl vector<pl>
#define ll long long
#define MAX 2147000000
#define MOD 1000000007
using namespace std;
struct st{
int l, r, idx;
};
int n, q;
const int sz = 1e5 + 10;
vector<st> query(sz);
vi A;
vl maxSeg(sz * 4);
vi vec;
void update(ll p, ll val)
{
for(maxSeg[p+=n]+=val;p>1;p>>=1) maxSeg[p>>1] = max(maxSeg[p], maxSeg[p^1]);
}
void Plus(int k){
update(k, A[k]);
}
void Minus(int k){
update(k, -A[k]);
}
int main() {
fastio;
cin >> n >> q;
vec.resize(n);
for(int i{0}; i < n; ++i){
cin >> vec[i];
}
A = vec;
sort(A.begin(), A.end());
A.erase(unique(A.begin(), A.end()), A.end());
for(int i{0}; i < n; ++i){
vec[i] = lower_bound(A.begin(), A.end(), vec[i]) - A.begin();
}
for(int i{0}; i < q; ++i){
cin >> query[i].l >> query[i].r;
query[i].l--; query[i].r--;
query[i].idx = i;
}
int sq = sqrt(n);
sort(query.begin(), query.begin() + q, [&](st& a, st& b){
if(a.l / sq == b.l / sq) return a.r < b.r;
else return a.l / sq < b.l / sq;
});
int l = query[0].l;
int r = query[0].r;
vl ans(q);
for(int i{l}; i <= r; ++i){
Plus(vec[i]);
}
ans[query[0].idx] = maxSeg[1];
for(int i{1}; i < q; ++i){
while(l > query[i].l) Plus(vec[--l]);
while(r < query[i].r) Plus(vec[++r]);
while(l < query[i].l) Minus(vec[l++]);
while(r > query[i].r) Minus(vec[r--]);
ans[query[i].idx] = maxSeg[1];
}
for(auto& i : ans) cout << i << "\n";
}
