#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, set<ll>> v;
for(int i = 0; i < n; i++){
v[-s[i]].insert(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;
}
while(v[ s[i] ].size() == 0) i++;
ans += *(v[s[i]].begin())-i+rg(segtree, i, *(v[s[i]].begin()), t);
if(s[i] < 0) ans--; //not need to swap shoes
//~ cerr << i << " " << *v[ s[i] ].begin() << " " << ans << "\n";
pos[i] = 1;
upd(segtree, *(v[s[i]].begin()) , t);
pos[ *(v[s[i]].begin()) ] = 1;
v[ s[*v[ s[i] ].begin()] ].erase(i);
v[ -s[i] ].erase( *v[ s[i] ].begin());
}
return ans;
}
