#include <bits/stdc++.h>
#include <shoes.h>
using namespace std;
#define f first
#define s second
#define pii pair<int, int>
#define long long long
#define v vector
#define rep(i,a,b) for(int i=a; i<b; i++)
struct segtree{
int N;
vector<long> arr;
segtree(int n){
N=n;
arr.assign(4*N, 0LL);
}
void update(int i, int val){
update(i, val, 0, 0, N);
}
void update(int i, int val, int cur, int lx, int rx){
if(rx-lx==1){
arr[cur]=val; return;
}
int mid= (lx+rx)/2;
if(mid>i) update(i, val, 2*cur+1, lx, mid);
else update(i, val, 2*cur+2, mid, rx);
arr[cur]= arr[cur*2+1]+arr[cur*2+2];
}
long sum (int l, int r){
return sum(l,r,0, 0, N);
}
long sum(int l, int r, int cur, int lx, int rx){
if(lx>=r || rx<=l) return 0;
if(lx>=l && rx<=r) return arr[cur];
int mid= (lx+rx)/2;
return sum(l,r,2*cur+1, lx, mid)+sum(l,r,2*cur+2, mid, rx);
}
};
int N;
map<int, set<int>> tmw;
long count_swaps(vector<int> arr){
N=arr.size();
for (int i = 0; i < N; ++i)
{
tmw[arr[i]].insert(i);
}
/*for(auto x= tmw.begin(); x!=tmw.end(); x++){
cout<<x->f;
for(int num: x->s){
cout<<" "<<num;
}
cout<<endl;
}
*/
long total=0;
segtree st= segtree(N);
for (int i = 0; i < N; ++i)
{
if(arr[i]==0) continue;
auto endpt=tmw[-arr[i]].lower_bound(i);
int end=*endpt;
tmw[-arr[i]].erase(end);
//cout<<end<<endl;
st.update(end, 1);
int free= st.sum(i, end);
if(arr[i]<0) total--;
arr[i]=0;
arr[end]=0;
total+=end-i-free;
}
return total;
}
