#include<bits/stdc++.h>
using namespace std;
const int BUC = 700;
int n,q;
int a[300005];
int fr[300005];
pair<pair<int,int>,int> qrys[300005];
long long rez[300005];
bool cmp(pair<pair<int,int>,int> x, pair<pair<int,int>,int> y)
{
if(x.first.second / BUC != y.first.second / BUC)
return x.first.second < y.first.second;
if((x.first.second / BUC) % 2 == 0)
return x.first.first < y.first.first;
else
return x.first.first > y.first.first;
}
int frfr[300005];
set<int> active;
void baga(int x)
{
frfr[fr[x]]--;
if(frfr[fr[x]]==0)
active.erase(fr[x]);
fr[x]++;
frfr[fr[x]]++;
if(frfr[fr[x]]==1)
active.insert(fr[x]);
}
void scoate(int x)
{
frfr[fr[x]]--;
if(frfr[fr[x]]==0)
active.erase(fr[x]);
fr[x]--;
frfr[fr[x]]++;
if(frfr[fr[x]]==1)
active.insert(fr[x]);
}
long long prec[300005];
long long calc(long long deja, long long noi, long long tot, long long siz)
{
long long sum=0;
sum += noi * (deja*tot - deja*deja - siz*siz);
sum += noi*(noi+1)/2 * (-deja*siz + siz*tot);
sum += noi*(noi-1)/2 * (-deja*siz);
sum -= prec[noi]*siz*siz;
return sum;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
for(long long i=2;i<=n;i++)
prec[i] = prec[i-1] + i*(i-1);
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=q;i++)
{
cin>>qrys[i].first.first>>qrys[i].first.second;
qrys[i].second = i;
}
sort(qrys+1,qrys+1+q,cmp);
int cle=1,cri=0;
for(int pas=1;pas<=q;pas++)
{
int qle = qrys[pas].first.first, qri = qrys[pas].first.second, qid = qrys[pas].second;
while(cri < qri)
{
cri++;
baga(a[cri]);
}
while(cle > qle)
{
cle--;
baga(a[cle]);
}
while(cle < qle)
{
scoate(a[cle]);
cle++;
}
while(cri > qri)
{
scoate(a[cri]);
cri--;
}
long long cntle=0,cntri=0,tot=0;
for(long long it:active)
{
long long noi = frfr[it];
tot += noi*(it*(it+1)/2);
assert(noi > 0);
if(cntle <= cntri)
{
tot += calc(cntle, (noi+1)/2, qri-qle+1, it);
tot += calc(cntri, noi/2, qri-qle+1, it);
cntle += ((noi+1)/2)*it;
cntri += (noi/2)*it;
}
else
{
tot += calc(cntri, (noi+1)/2, qri-qle+1, it);
tot += calc(cntle, noi/2, qri-qle+1, it);
cntri += ((noi+1)/2)*it;
cntle += (noi/2)*it;
}
}
rez[qid] = tot;
}
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
