#include "bits/stdc++.h"
using namespace std;
#define ar array
#define int int64_t
const int N = 3e5 + 5;
const int Q = 5e4 + 5;
const int B = 550;
int a[N], l[Q], r[Q];
int cnt[N], res[Q];
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=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];
});
map<int, int> mm;
auto add = [&](int i){
if(cnt[a[i]]){
mm[cnt[a[i]]]--;
if(!mm[cnt[a[i]]]) mm.erase(cnt[a[i]]);
}
cnt[a[i]]++;
mm[cnt[a[i]]]++;
};
auto del = [&](int i){
assert(cnt[a[i]]);
mm[cnt[a[i]]]--;
if(!mm[cnt[a[i]]]) mm.erase(cnt[a[i]]);
cnt[a[i]]--;
if(cnt[a[i]]) mm[cnt[a[i]]]++;
};
int lx = 0, rx = 0;
for(auto i : p){
while(rx > r[i]){
del(--rx);
}
while(rx < r[i]){
add(rx++);
}
while(lx > l[i]){
add(--lx);
}
while(lx < l[i]){
del(lx++);
}
int ls = 0, rs = 0;
deque<ar<int, 2>> L, R;
for(auto [v, c] : mm){
int b = (c + 1) / 2, s = c - b;
if(ls > rs) swap(b, s);
if(b) L.push_back({v, b}), ls += b;
if(s) R.push_front({v, s}), rs += s;
}
L.insert(L.end(), R.begin(), R.end());
//~ for(auto x : L) cout<<x[0]<<" "<<x[1]<<"\n";
int sum = 0, sumj = 0, p = 0;
for(auto [v, c] : L){
res[i] += v * (p * c + c * (c - 1) / 2) * sum;
res[i] -= v * sumj;
res[i] += (c * c * (c + 1) / 2 - c * (c + 1) * (2 * c + 1) / 6) * v * v;
sumj += v * (p * c + c * (c - 1) / 2);
p += c, sum += v * c;
}
res[i] += sum * (sum + 1) / 2;
//~ cout<<"\n";
}
for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}
