#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);
void build(int node,int start,int end){
if(start==end){
seg[node] = start;
return;
}
int mid = (start+end)/2;
build(node*2+1,start,mid);build(node*2+2,mid+1,end);
seg[node] = seg[node*2+1];
}
void update(int node,int start,int end,int pos,int val){
if(start==end){
num[start] += val;
return;
}
int mid = (start+end)/2;
if(pos<=mid){
update(node*2+1,start,mid,pos,val);
}
else{
update(node*2+2,mid+1,end,pos,val);
}
if(num[seg[node*2+1]]>=num[seg[node*2+2]]){
seg[node] = seg[node*2+1];
}
else{
seg[node] = seg[node*2+2];
}
}
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);
}
build(0,0,n-1);
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}});
}
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--;
update(0,0,n-1,vect1[l],compress[vect1[l]]);
}
while(l<k.s.f){
update(0,0,n-1,vect1[l],-compress[vect1[l]]);
l++;
}
while(r<k.f){
r++;
update(0,0,n-1,vect1[r],compress[vect1[r]]);
}
while(r>k.f){
update(0,0,n-1,vect1[r],-compress[vect1[r]]);
r--;
}
ans[k.s.s] = num[seg[0]];
}
}
for(int i=0;i<m;i++){
cout << ans[i] << "\n";
}
}
