#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 300000
#define inf (int)1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
const int kok=320;
struct Item{
int l,r,i;
Item(int ll,int rr,int ii){
l=ll;r=rr;i=ii;
}
bool operator <(Item other){
return make_pair(l/kok,r)<make_pair(other.l/kok,other.r);
}
};
void solve(){
int n,q;
cin >> n >> q;
int a[n+1];
vector<Item> query;
for(int i=1;i<=n;i++)
cin >> a[i];
for(int i=0;i<q;i++){
int l,r;
cin >> l >> r;
query.emb(l,r,i);
}
sort(all(query));
map<int,int> mp,s;
int l=1,r=1,ans[q];
auto del=[&s](int x){
if(s.find(x)!=s.end()){
if(s[x]==1) s.erase(x);
else s[x]--;
}
};
auto add=[&s](int x){
if(x>0) s[x]++;
};
for(auto [ql,qr,i]:query){
while(r<qr+1){
del(a[r]*mp[a[r]]);
++mp[a[r]];
add(a[r]*mp[a[r]]);
++r;
}
while(r>qr+1){
--r;
del(a[r]*mp[a[r]]);
--mp[a[r]];
add(a[r]*mp[a[r]]);
}
while(l<ql){
del(a[l]*mp[a[l]]);
--mp[a[l]];
add(a[l]*mp[a[l]]);
++l;
}
while(l>ql){
--l;
del(a[l]*mp[a[l]]);
++mp[a[l]];
add(a[l]*mp[a[l]]);
}
//~ cout << ql sp qr sp i << "\n";
//~ cout << ":" sp l sp r << "\n";
//~ for(auto i:mp)
//~ cout << i.fr sp i.sc << "\n";
//~ cout << "------\n";
//~ for(auto i:s)
//~ cout << i.fr sp i.sc << "\n";
//~ cout << "\n";
ans[i]=s.rbegin()->fr;
}
for(int i=0;i<q;i++)
cout << ans[i] << "\n";
}
int32_t main(){
//~ freopen("hopscotch.in","r",stdin);
//~ freopen("hopscotch.out","w",stdout);
cout << fixed << setprecision(0);
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;
//~ cin >> test;
while(test--) solve();
}
