#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<char,char> pcc;
typedef pair<pii,int> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int SQRT = 600;
const int MAXA = 1e5;
const int LOG = 20;
const int INF = 1e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int n, q, a[MAXN], cnt[MAXN];
int siz;
vector <ipii> que;
bool cmp(ipii a, ipii b){
if(a.fi.fi/SQRT != b.fi.fi/SQRT) a.fi.fi/SQRT < b.fi.fi/SQRT;
return a.fi.se < b.fi.se;
}
int l=1,r=0, dif[MAXN];
set<int> ma;
void move(int le, int ri){
while(le < l){
l--;
dif[cnt[a[l]]]--;
if(dif[cnt[a[l]]] == 0) ma.erase(cnt[a[l]]);
cnt[a[l]]++;
dif[cnt[a[l]]]++;
if(dif[cnt[a[l]]] == 1) ma.insert(cnt[a[l]]);
}
while(r < ri){
r++;
dif[cnt[a[r]]]--;
if(dif[cnt[a[r]]] == 0) ma.erase(cnt[a[r]]);
cnt[a[r]]++;
dif[cnt[a[r]]]++;
if(dif[cnt[a[r]]] == 1) ma.insert(cnt[a[r]]);
}
while(l < le){
if(dif[cnt[a[l]]] == 1) ma.erase(cnt[a[l]]);
dif[cnt[a[l]]]--;
cnt[a[l]]--;
if(dif[cnt[a[l]]] == 0) ma.insert(cnt[a[l]]);
dif[cnt[a[l]]]++;
l++;
}
while(ri < r){
if(dif[cnt[a[r]]] == 1) ma.erase(cnt[a[r]]);
dif[cnt[a[r]]]--;
cnt[a[r]]--;
if(dif[cnt[a[r]]] == 0) ma.insert(cnt[a[r]]);
dif[cnt[a[r]]]++;
r--;
}
}
ll dua(ll x){ return 1ll*x*(x+1)/2; }
ll tiga(ll x){ return 1ll*x*(x+1)*(2*x+1)/6; }
pii opt[MAXN];
ll ans[MAXN];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1; i<=n; i++)
cin>>a[i];
for(int p=1; p<=q; p++){
int l,r;cin>>l>>r;
que.pb({{l,r}, p});
}
sort(que.begin(), que.end(), cmp);
for(auto [xx, idx] : que){
move(xx.fi, xx.se);
vector <pii> vec;
ll run = 0, lenreal = 0;
for(auto in : ma){
vec.pb(pii(in, dif[in])); // value, len
lenreal += 1ll*in*dif[in];
// cout << in << ' ' << dif[in] << " dif\n";
}
// cout << lenreal << " lenreal\n";
reverse(vec.begin(), vec.end());
assert(vec.empty() < 2*SQRT);
int L = MAXA, R = MAXA; bool isle = 1; // terakhir ada di left?
opt[L] = vec[0];
for(int i=0; i<vec.size(); i++){
auto [val, len] = vec[i];
run += 1ll * len * val*(lenreal-val);
run += 1ll * len * val*(val+1)/2;
if(i==0) continue;
int a, b;
if((len & 1) == 0) a = len/2, b = len/2;
else {
if(isle) a = len/2, b = len/2+1, isle = 0; // right nambahin
else a = len/2+1, b = len/2, isle = 1; // left tambahin, ke left
}
if(a!=0) opt[--L] = pii(val, a);
if(b!=0) opt[++R] = pii(val, b);
}
// cout << run << " RUNN\n";
vector <pii> seg; seg.pb({-1,-1}); vector <ll> pr; pr.pb(0);
for(int i=L; i<=R; i++){
// cout << i << ' ' << opt[i].fi<<' '<<opt[i].se << " opt\n";
seg.pb(opt[i]);
pr.pb(pr.back() + 1ll*opt[i].se*opt[i].fi);
}
pr.pb(-INF);
vector <ll> su; su.resize(pr.size()); su.back() = 0;
for(int i=R; i>=L; i--)
su[i-L+1] = (su[i-L+2] + 1ll*opt[i].se*opt[i].fi);
su[0] = -INF;
// for(auto in : pr) cout<<in<<' ';
// cout << '\n';
// for(auto in : su) cout << in<<' ';
// cout << '\n';
// cout << seg.size()<< " seg\n";
ll val = 0;
for(int i=1; i<seg.size(); i++){
auto [v, len] = seg[i];
int p = pr[i-1], q = su[i+1], lenv = len*v-v;
ll nw = 1ll*len*p*(q+lenv) + 1ll*(q+lenv-p)*v*dua(len-1)
- 1ll*v*v*tiga(len-1);
// cout << i << ' ' << nw << " nw\n";
// cout << len*p*(q+lenv) << ' '<< (q+lenv-p)*v*dua(len-1)
// << ' '<< - v*v*tiga(len-1) << "nwjuga\n";
val += nw;
}
// cout << val << ' '<< run << "\n\n";
ans[idx] = val + run;
}
for(int i=1; i<=q; i++) cout << ans[i] << '\n';
}
/*
int ans = 0;
for(int i=1; i<=300000; i++){
int len = cnt[i];
ans += len * (n-len);
ans += len*(len+1)/2;
if(cnt[i] != 0) vec.pb(cnt[i]);
}
sort(vec.rbegin(), vec.rend());
siz = vec.size();
opt.resize(siz);
int l=siz/2, r=siz/2-1;
for(int i=0; i<siz; i++){
if(i%2==0) opt[++r] = vec[i];
else opt[--l] = vec[i];
}
// for(auto in : opt) cout << in << ' ';
// cout << '\n';
for(int i=0; i<siz; i++){
if(i!=0) pr[i] = pr[i-1]+opt[i];
else pr[i] = opt[i];
}
for(int i=siz-1; i>=0; i--)
su[i] = su[i+1]+opt[i];
int nw = 0;
for(int i=0; i<siz; i++){
nw += (i==0?0:pr[i-1]) * (i+1==siz?0:su[i+1]);
}
cout << run+nw << '\n';
*/
