#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;
const ll MAXS = 5e5+10;
ll BIT[MAXS];
bool vis[MAXS];
ll n;
unordered_map<ll, set<ll>> ma; //numi, original pos
void updrange(ll pos, ll delta){
ll it=pos;
while(it<=n){
BIT[it] += delta;
it += (it & -it);
}
}
ll query(ll pos){
ll res=0;
while(pos > 0){
res+=BIT[pos];
pos -= (pos & -pos);
}
return res;
}
ll count_swaps(std::vector<int> s) {
n=s.size();
for (ll i=0; i<n; i++)
ma[s[i]].insert(i);
for (ll i=0; i<n-1; i++){
if (vis[i]) continue;
vis[i]=1;
auto ff=ma[s[i]].begin();
ma[s[i]].erase(ff);
if (s[i]>0){
auto fopp=ma[s[i]*-1].begin();
ll cpos=i + query(i+1);
ll copppos=*fopp + query(*fopp + 1);
ll origopppos=*fopp;
ma[s[i]*-1].erase(fopp);
ll diff=copppos - cpos;
ans+=diff;
//cout<<"\t"<<diff<<' '<<cpos<<' '<<copppos<<' '<<origopppos<<endl;
updrange(i+1, 1);
updrange(origopppos+1, -1);
vis[origopppos]=1;
}else{
auto fopp=ma[s[i]*-1].begin();
ll cpos=i + query(i+1);
ll copppos=*fopp + query(*fopp + 1);
ll origopppos=*fopp;
ma[s[i]*-1].erase(fopp);
ll diff=copppos - cpos - 1;
ans+=diff;
vis[origopppos]=1;
if (diff>0){
updrange(i+2, 1);
updrange(origopppos+1, -1);
}
}
}
return ans;
}
