#include<bits/stdc++.h>
using namespace std;
#define int long long
const int BUC = 550;
const int MAXV = 3e5;
int n,q;
int a[300005];
int fr[300005];
bool isbig[300005];
pair<pair<int,int>,int> qrys[300005];
int 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;
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]);
}
int calc(int deja, int noi, int tot, int siz)
{
int sum=0;
for(int i=1;i<=noi;i++)
{
int le = deja + (i-1)*siz;
int ri = tot - (deja + i*siz);
sum += le*ri + siz*le + siz*ri;
}
return sum;
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>q;
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--;
}
int cntle=0,cntri=0,tot=0;
//cerr<<"\n\n";
for(auto it:active)
{
int noi = frfr[it];
//cerr<<it<<" "<<noi<<" it & noi\n";
tot += noi*(it*(it+1)/2);
assert(noi > 0);
//assert(abs(cntle-cntri)<=1);
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;
}
//cerr<<cntle<<" "<<cntri<<" cntle & cntri\n";
}
rez[qid] = tot;
}
for(int i=1;i<=q;i++)
cout<<rez[i]<<"\n";
return 0;
}
