#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
#define index int med=(s+e)/2,l=2*n+1,r=2*n+2
typedef long long ll;
const int tam=1e5;
unordered_map<int,priority_queue<int,vector<int>,greater<int>>> ma;
vector<int> tr(4*tam);
void init(int n, int s, int e){
if(s==e){
tr[n]=1;
return;
}
index;
init(l,s,med); init(r,med+1,e);
tr[n]=tr[l]+tr[r];
}
void update(int n, int s, int e, int pos, vector<int> &v){
if(s==e){
v[s]=0;
tr[n]=0;
return;
}
index;
if(pos<=med) update(l,s,med,pos,v);
else update(r,med+1,e,pos,v);
tr[n]=tr[l]+tr[r];
}
int query(int n, int s, int e, int i, int j){
if(i>j) return 0;
if(i<=s && e<=j) return tr[n];
index;
if(j<=med) return query(l,s,med,i,j);
if(i>med) return query(r,med+1,e,i,j);
return query(l,s,med,i,j)+query(r,med+1,e,i,j);
}
long long count_swaps(std::vector<int> s) {
int n=s.size();
for(int i=0;i<n;i++) ma[s[i]].push(i);
init(0,0,n-1);
ll res=0;
vector<bool> vis(n,false);
for(int i=0;i<n;i++){
if(vis[i]) continue;
int j=ma[-s[i]].top();
ma[-s[i]].pop();
ma[s[i]].pop();
vis[j]=true;
int moves=query(0,0,n-1,i+1,j-1)+(s[i]>0);
res+=moves;
update(0,0,n-1,j,s);
}
return res;
}
