#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
typedef long long ll;
int sqrtN;
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
bool operator<(const Query &tmp)const{
if(l/sqrtN != tmp.l/sqrtN) return l < tmp.l;
return r < tmp.r;
}
};
int n, q, k;
ll arr[100002];
vector<Query> vec;
ll cnt[100002];
ll ans[100002];
vector<ll> v;
ll tree[400002];
inline void update(int i, ll val){
tree[i+=131072] += val;
for(i/=2; i; i/=2) {
tree[i] = max(tree[i*2], tree[i*2+1]);
}
}
inline void removeNum(ll x){
update(x, -v[x]);
}
inline void addNum(ll x){
update(x, v[x]);
}
void renumber(){
for(int i=0; i<n; i++) v.push_back(arr[i]);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i=0; i<n; i++) arr[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
k = (int)v.size();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q;
sqrtN = ceil(sqrt(n));
for(int i=0; i<n; i++) cin >> arr[i];
renumber();
for(int i=1; i<=q; i++){
int l, r;
cin >> l >> r;
l--, r--;
vec.push_back(Query(l, r, i));
}
sort(vec.begin(), vec.end());
int s = 0, e = -1;
for(int i=0; i<q; i++){
Query tmp = vec[i];
int l = tmp.l, r = tmp.r, idx = tmp.idx;
while(e < r) addNum(arr[++e]);
while(s > l) addNum(arr[--s]);
while(e > r) removeNum(arr[e--]);
while(s < l) removeNum(arr[s++]);
ans[idx] = tree[1];
}
for(int i=1; i<=q; i++){
cout << ans[i] << '\n';
}
}
