#include <bits/stdc++.h>
#define MAX 305000
#define SQRT 800
using ll = long long;
ll array[MAX],freq[MAX];
ll N,Q;
typedef std::pair<ll,ll> pii;
typedef std::pair<pii,ll> ppi;
ll l[MAX],r[MAX],resp[MAX];
std::vector<ppi> queries;
ll sizes[MAX];
std::vector<ll> casos;
ll foier[MAX];
bool pesado[MAX];
void add(ll x){
ll elemento = array[x];
if(!pesado[elemento])
sizes[freq[elemento]]--;
++freq[elemento];
if(!pesado[elemento])
sizes[freq[elemento]]++;
}
void remove(ll x){
ll elemento = array[x];
if(!pesado[elemento])
sizes[freq[elemento]]--;
--freq[elemento];
if(!pesado[elemento])
sizes[freq[elemento]]++;
}
ll rodanda=42;
ll precomp[MAX];
typedef std::pair<ll,ll> pll;
ll gaussian(ll first,ll last,ll size){
return (first+last)*size/2LL;
}
std::vector<ll> separado;
ll getans(ll length){
++rodanda;
std::vector<pii> sz;
ll base=0;
for(ll i=1;i!=SQRT;++i){
base+=((i*(i+1))/2)*sizes[i];
if(sizes[i]){
sz.push_back({i,sizes[i]});
}
}
std::vector<pii> secondary;
for(auto&x:separado){
if(freq[x]){
base+=((freq[x]*(freq[x]+1))/2);
secondary.push_back({freq[x],1});
}
}
std::random_shuffle(secondary.begin(),secondary.end());
std::sort(secondary.begin(),secondary.end());
int c1=sz.size()-1,c2=secondary.size()-1;
std::deque<pll> ans;
ll count=0;
for(ll i = 0;i!=sz.size()+secondary.size();++i){
ll agora = count&1;
pii analise;
pii a1={-1,-1},a2={-1,-1};
if(c1>=0){
a1=sz[c1];
}
if(c2>=0){
a2=secondary[c2];
}
if(a1>a2){
analise=a1;
--c1;
}else {
analise=a2;
--c2;
}
ll metade_maior = analise.second/2 + (analise.second%2);
ll metade_menor = analise.second/2;
if(agora){
ans.push_back({analise.first,metade_maior});
ans.push_front({analise.first,metade_menor});
}else {
ans.push_front({analise.first,metade_maior});
ans.push_back({analise.first,metade_menor});
}
count+=analise.second;
}
ll res=0,somado=0;
ll foi=0;
for(ll i=0;i!=ans.size();++i){
ll tam = ans[i].first;
ll sum_somado=gaussian(somado,somado+(ans[i].second-1)*ans[i].first,ans[i].second);
ll sum_foi = gaussian(foi,foi+(ans[i].second-1),ans[i].second);
res+=ans[i].first*sum_somado;
res+=sum_foi*ans[i].first*ans[i].first;
res-=length*ans[i].first*sum_foi;
ll s=0;
ll tenta_prever=0,brute=0;
if(ans[i].second)
{
ll iteracoes = gaussian(0,ans[i].second-1,ans[i].second);
ll tamk = iteracoes*tam;
tenta_prever=ans[i].second*somado*foi;
tenta_prever+=somado*iteracoes;
tenta_prever+=iteracoes*tam*foi;
tenta_prever+=tam*precomp[ans[i].second-1];
}
tenta_prever*=2*tam;
res+=tenta_prever;
foi+=ans[i].second;
somado+=tam*ans[i].second;
}
return base+res;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
for(ll i=1;i!=MAX;++i){
precomp[i]=precomp[i-1]+i*i;
}
std::map<int,int> aparece;
std::cin>>N>>Q;
for(ll i=0;i!=N;++i){
std::cin>>array[i];
aparece[array[i]]++;
}
std::vector<pii> mais_frequentes;
for(auto&x:aparece)mais_frequentes.push_back({x.second,x.first});
std::sort(mais_frequentes.begin(),mais_frequentes.end());
std::reverse(mais_frequentes.begin(),mais_frequentes.end());
for(int i=0;i<std::min((ll)mais_frequentes.size(),(ll)SQRT);++i){
separado.push_back(mais_frequentes[i].second);
pesado[mais_frequentes[i].second]=1;
}
for(ll i=0;i!=Q;++i){
std::cin>>l[i]>>r[i];
--l[i];--r[i];
queries.push_back({{l[i]/600,r[i]},i});
}
std::sort(queries.begin(),queries.end());
ll curl=0,curr=-1;
for(auto&x:queries){
ll querl = l[x.second],querr=r[x.second];
ll ans=0;
while(curr<querr){///Vai para a direita removendo elementos
++curr;
add(curr);
}
while(curl>querl){///Diminui o cursor aumentando elementos
--curl;
add(curl);
}
while(curl<querl){///Vai para a direita removendo elementos
remove(curl);
++curl;
}
while(curr>querr){///Diminui o cursor diminuindo elementos
remove(curr);
--curr;
}
ans=getans(querr-querl+1);
resp[x.second]=ans;
}
for(ll i=0;i!=Q;++i){
std::cout<<resp[i]<<"\n";
}
}
