#include <bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
#define sqrtn 320
#define f first
#define s second
vector<int> seg(maxn*4,0);
vector<int> num(maxn,0);
vector<int> compress;
vector<int> vect1;
vector<int> ans(maxn,0);
vector<vector<pair<int,pair<int,int> > > > queries(sqrtn);
priority_queue<int> ins,del;
void insert(int node){
//cout << node << endl;
num[node] += compress[node];
ins.push(num[node]);
}
void deleter(int node){
//cout << node << endl;
del.push(num[node]);
num[node] -= compress[node];
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n,m;
int input;
cin >> n >> m;
for(int i=0;i<n;i++){
cin >> input;
compress.push_back(input);
vect1.push_back(input);
}
sort(compress.begin(),compress.end());
for(int i=0;i<n;i++){
vect1[i] = lower_bound(compress.begin(),compress.end(),vect1[i])-compress.begin();
}
int a,b;
for(int i=0;i<m;i++){
cin >> a >> b;
a--,b--;
queries[a/sqrtn].push_back({b,{a,i}});
}
//cout << "YES" << endl;
int l = 0,r = -1;
for(int i=0;i<sqrtn;i++){
sort(queries[i].begin(),queries[i].end());
for(auto k:queries[i]){
while(l>k.s.f){
l--;
insert(vect1[l]);
}
while(l<k.s.f){
deleter(vect1[l]);
l++;
}
while(r<k.f){
r++;
insert(vect1[r]);
}
while(r>k.f){
deleter(vect1[r]);
r--;
}
while(del.size()>0&&ins.top()==del.top()){
ins.pop();
del.pop();
}
ans[k.s.s] = ins.top();
// cout << "YES" << endl;
}
}
for(int i=0;i<m;i++){
cout << ans[i] << "\n";
}
}
