#include <bits/stdc++.h>
#define ll long long
#define loop(i, a, b) for(ll i=a;i<b;++i)
#define pool(i, a, b) for(ll i=a-1;i>=b;--i)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define eb(...) emplace_back(__VA_ARGS__)
#define sc scanf
#define vc vector
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 500100
#define par pair<ll, ll>
#define ld long double
#define mod 1000000007
ll cnt[300100];
int main() {
ll n, q;cin >> n >> q;
vc<ll> a(n);loop(i, 0, n) cin >> a[i];
vc<array<ll, 3>> que(q);
loop(i, 0, q){ cin >> que[i][0] >> que[i][1];--que[i][0], --que[i][1];}
loop(i, 0, q) que[i][2]=i;
const ll m=550;
sort(all(que), [&](array<ll, 3> a, array<ll, 3> b){
if(a[0]/m==b[0]/m) return a[1]<b[1];
return a[0]<b[0];
});
set<ll> act;
function<void (ll)> add=[&](ll i){
act.insert(a[i]);
++cnt[a[i]];
};
function<void (ll)> rem=[&](ll i){
--cnt[a[i]];
if(cnt[a[i]]==0) act.erase(a[i]);
};
function<ll ()> getans=[&](){
ll sum=0;
vc<ll> cs; fore(v, act) sum+=cnt[v], cs.ps(cnt[v]);
sort(all(cs));
ll ret=0;
vc<ll> pre(2, 0);
loop(i, 0, cs.size()){
ret+=pre[i%2] * (sum-cs[i]-pre[i%2]);
pre[i%2]+=cs[i];
ret+=cs[i] * (sum-cs[i]);
ret+=(cs[i] * cs[i] + cs[i])/2;
}
return ret;
};
vc<ll> ans(q);
ll l=0, r=-1;
loop(i, 0, q){
ll ql=que[i][0], qr=que[i][1];
while(r<qr) add(++r);
while(r>qr) rem(r--);
while(l<ql) rem(l++);
while(l>ql) add(--l);
ans[que[i][2]]=getans();
}
loop(i, 0, q) cout << ans[i]<<endl;
}
