#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll=long long;
const int N=2e5;
int bit[N+5];
int b[N+5],d[N+5];
map<int,vector<int>>pos;
map<int,int>f;
int n;
void upd(int idx,int val){for(;idx<=n;idx+=(idx&-idx))bit[idx]+=val;}
int get(int idx){int res=0;for(;idx>0;idx-=(idx&-idx))res+=bit[idx];return res;}
ll count_swaps(vector<int>a){
for(int i=1;i<=N;++i)bit[i]=0;
n=(int)a.size();
int n1=0;
for(int i=1;i<=n;++i){
int x=a[i-1];
// cout<<x<<' '<<f[x]<<'\n';
if(f[-x]<=f[x]){
b[++n1]=-abs(x);
b[++n1]=abs(x);
}
f[x]++;
}
// for(int i=1;i<=n;++i)cout<<b[i]<<' ';
// cout<<'\n';
for(int i=n;i>=1;--i){
pos[b[i]].push_back(i);
}
for(int i=1;i<=n;++i){
d[i]=pos[a[i-1]].back();
pos[a[i-1]].pop_back();
//cout<<d[i]<<' ';
}
// cout<<'\n';
ll ans=0;
for(int i=1;i<=n;++i){
upd(d[i],1);
ans+=(ll)i-get(d[i]);
// cout<<ans<<" "<<get(d[i])<<'\n';
}
return ans;
}
//int main(){
// freopen("task.inp","r",stdin);
// freopen("task.out","w",stdout);
// vector<int>v;
// for(int x;cin>>x;){
// v.push_back(x);
// }
// cout<<count_swaps(v);
// return 0;
//}
