#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
//sl : increase from l
//sr : increase from r
const int mx=300000,MID=150000,sq=1350;
struct NN {
ll sum,sl,sr,cnt;
} s[1<<21];
int ccnt[mx+5],posi[mx+5],num[mx+5];
NN merge(NN a, NN b) {
NN res;
res.sum=a.sum+b.sum;
res.cnt=a.cnt+b.cnt;
res.sl=a.sl+a.cnt*b.sum+b.sl;
res.sr=b.sr+b.cnt*a.sum+a.sr;
return res;
}
void update(int l, int r, int idx, int x) {
if (x>r || x<l) return;
if (l==r) s[idx]={ccnt[l],ccnt[l],ccnt[l],1};
else {
int mid=(l+r)/2;
update(l,mid,2*idx,x);
update(mid+1,r,2*idx+1,x);
s[idx]=merge(s[2*idx],s[2*idx+1]);
}
}
ll fast_query(int l, int r, int idx, int x) {
if (x>r) return s[idx].sr+s[idx].sum*(ll)(x-r);
if (x<l) return s[idx].sl+s[idx].sum*(ll)(l-x);
if (l==r) return s[idx].sum;
int mid=(l+r)/2;
return fast_query(l,mid,2*idx,x)+fast_query(mid+1,r,2*idx+1,x);
}
int level[mx+5],have[mx+5],idx_seq=-1; //range of box that has been used
vector<int> seq;
deque<int> dq[mx+5];
ll ans=0;
void sw(int a, int b) {
swap(num[a],num[b]);
posi[num[a]]=a;
posi[num[b]]=b;
}
void add(int val) {
if (!have[val]) {
++idx_seq;
int pos=seq[idx_seq]; //the position of the seg-tree to be added
ccnt[pos]=1;
posi[val]=pos;
num[pos]=val;
update(1,mx,1,pos);
dq[1].push_back(pos);
ans+=fast_query(1,mx,1,pos);
} else {
int pos=posi[val], cnt=ccnt[pos]; //increase from cnt to cnt+1
int max_pos=dq[cnt].front();
sw(pos,max_pos);
//increase from cnt to cnt+1
dq[cnt].pop_front();
dq[cnt+1].push_back(max_pos);
++ccnt[max_pos];
update(1,mx,1,max_pos);
ans+=fast_query(1,mx,1,max_pos);
}
++have[val];
}
void del(int val) {
int pos=posi[val], cnt=ccnt[pos];
int min_pos=dq[cnt].back();
sw(pos,min_pos);
ans-=fast_query(1,mx,1,min_pos);
dq[cnt].pop_back();
if (cnt==1) --idx_seq;
else dq[cnt-1].push_front(min_pos);
--ccnt[min_pos];
update(1,mx,1,min_pos);
--have[val];
}
int n,q,a[mx+5];
struct Query {
int l,r,idx;
bool operator<(Query other) const {
return pii(l/sq,((l/sq)&1) ? -r : +r)<pii(other.l/sq,((other.l/sq)&1) ? -other.r : +other.r);
}
};
vector<Query> ques;
ll Ans[50005];
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int ll=MID,rr=MID;
level[MID]=0;
seq.push_back(MID);
for (int i=1; i<mx; ++i) {
if (i%2==0) level[--ll]=i, seq.push_back(ll);
else level[++rr]=i, seq.push_back(rr);
}
cin>>n>>q;
for (int i=0; i<n; ++i) cin>>a[i];
for (int i=0; i<q; ++i) {
int l,r; cin>>l>>r;
ques.push_back({--l,--r,i});
}
sort(ques.begin(),ques.end());
int cur_l=0;
int cur_r=-1;
for (auto q : ques) {
while (cur_l>q.l) add(a[--cur_l]);
while (cur_r<q.r) add(a[++cur_r]);
while (cur_l<q.l) del(a[cur_l++]);
while (cur_r>q.r) del(a[cur_r--]);
Ans[q.idx]=ans;
}
for (int i=0; i<q; ++i) cout<<Ans[i]<<"\n";
}
