#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
ll get(ll x){
ll y = 0;
while((1ll<<y) < x) y++;
return (1ll << y);
}
void upd(vector<ll> & segtree, ll a, ll t){
a += t;
while(a > 0){
segtree[a]++;
a/=2;
}
}
ll rg(vector<ll> & segtree, ll a, ll b, ll t){
a += t, b += t;
ll ans = 0;
while(a <= b){
if(a % 2 == 1) ans += segtree[a++];
if(b % 2 == 0) ans += segtree[b--];
a /= 2, b/= 2;
}
return ans;
}
long long count_swaps(std::vector<int> s) {
ll n = s.size();
map<ll, deque<ll>> v;
for(int i = 0; i < n; i++){
v[-s[i]].push_back(i);
}
ll t = get(n);
vector<ll> segtree(2*t);
vector<bool> pos(n, 0);
ll ans = 0;
for(int i = 0; i < n; i++){
if(pos[i]){
continue;
}
ans += v[s[i]][0]-i-rg(segtree, i, v[s[i]][0], t);
if(s[i] < 0) ans--; //not need to swap shoes
pos[i] = 1;
upd(segtree, v[s[i]][0], t);
pos[ v[s[i]][0] ] = 1;
v[ -s[i] ].pop_front();
v[ s[i] ].pop_front();
}
return ans;
}
