#include "bits/stdc++.h"
using namespace std;
#define ar array
#define ll int64_t
const int N = 3e5 + 5;
const int Q = 5e4 + 5;
const int B = 1350;
int a[N], l[Q], r[Q], cnt[N];
int is[N], mm[N];
ll res[Q], dp[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, q; cin>>n>>q;
vector<int> p;
for(int i=0;i<n;i++){
cin>>a[i];
}
for(int i=1;i<N;i++){
dp[i] = dp[i-1] + (i * 1ll * (i - 1) / 2);
}
for(int i=0;i<q;i++){
cin>>l[i]>>r[i];
l[i]--;
p.push_back(i);
}
sort(p.begin(), p.end(), [&](int i, int j){
if(l[i] / B != l[j] / B){
return l[i] < l[j];
}
return r[i] < r[j];
});
set<int> ss;
auto add = [&](int i){
int& cur = cnt[a[i]];
if(cur){
mm[cur]--;
if(!mm[cur]) ss.erase(cur);
}
cur++;
if(!mm[cur]) ss.insert(cur);
mm[cur]++;
};
auto del = [&](int i){
//~ assert(cnt[a[i]]);
mm[cnt[a[i]]]--;
if(!mm[cnt[a[i]]]) ss.erase(cnt[a[i]]);
cnt[a[i]]--;
if(cnt[a[i]]){
if(!mm[cnt[a[i]]]) ss.insert(cnt[a[i]]);
mm[cnt[a[i]]]++;
}
};
int lx = 0, rx = 0;
for(auto i : p){
if(rx > r[i]){
ss.clear();
lx = rx = l[i];
memset(cnt, 0, sizeof cnt);
memset(mm, 0, sizeof mm);
}
while(rx < r[i]){
add(rx++);
}
while(lx > l[i]){
add(--lx);
}
while(lx < l[i]){
del(lx++);
}
int ls = 0, rs = 0;
vector<ar<ll, 2>> L, R;
for(auto v : ss){
int c = mm[v];
int b = (c + 1) / 2, s = c / 2;
if(ls > rs) swap(b, s);
if(b) L.push_back({v, b}), ls += b;
if(s) R.push_back({v, s}), rs += s;
}
reverse(R.begin(), R.end());
L.insert(L.end(), R.begin(), R.end());
ll sum = 0, sumj = 0, p = 0;
for(auto [v, c] : L){
ll C = p * c + c * (c - 1) / 2;
res[i] = res[i] + v * C * sum - v * c * sumj;
res[i] += dp[c] * v * v;
sumj += v * C;
sum += v * c;
p += c;
}
res[i] += sum * (sum + 1) / 2;
}
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
