#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll seg[400001];
ll query(ll id, ll l, ll r, ll x, ll y){
if (x<=l && r<=y) return seg[id];
if (l>y || r<x) return 0;
ll mid=(l+r)/2;
return query(id*2, l, mid, x, y)+query(id*2+1, mid+1, r, x, y);
}
void update(ll id, ll l, ll r, ll p){
if (l==r){
seg[id]++;
return;
}
ll mid=(l+r)/2;
if (p<=mid) update(id*2, l, mid, p);
else update(id*2+1, mid+1, r, p);
seg[id]=seg[id*2]+seg[id*2+1];
}
ll n, done[100001], ans=0;
set<ll> nxtl[100001], nxtr[100001];
ll count_swaps(vector<int> s){
n=s.size();
s.insert(s.begin(), 0);
for (int i=0; i<=4*n; i++) seg[i]=0;
for (int i=1; i<=n; i++){
if (s[i]<0) nxtl[-s[i]].insert(i);
else nxtr[s[i]].insert(i);
}
for (int i=1; i<=n; i++){
if (done[i]) continue;
if (s[i]<0){
if (s[i+1]==-s[i]){
i++;
continue;
}
int t=*(nxtr[-s[i]].lower_bound(i));
nxtr[-s[i]].erase(t);
done[t]=1;
ans+=t-i-1-query(1, 1, n, i, t);
update(1, 1, n, t);
}else{
int t=*nxtl[s[i]].lower_bound(i);
nxtl[s[i]].erase(t);
done[t]=1;
ans+=t-i-query(1, 1, n, i, t);
update(1, 1, n, t);
}
}
return ans;
}
