#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include "shoes.h"
using namespace std;
typedef long long ll;
vector<ll> t;
ll getSum(ll idx){
ll sum = 0;
idx++;
while (idx > 0){
sum += t[idx];
idx -= idx & (-idx);
}
return sum;
}
void updateF(ll n, ll idx, ll val){
idx++;
while (idx <= n){
t[idx] += val;
idx += idx & (-idx);
}
}
ll count_swaps(vector<int> s){
ll n = s.size();
t.assign(n + 1, 0);
vector<queue<ll>> cnt1(n + 1, queue<ll> ()), cnt2(n + 1, queue<ll> ());
queue<ll> q;
for (ll i = n - 1; i >= 0; i--){
if (s[i] < 0)
cnt2[-s[i]].push(i);
else
cnt1[s[i]].push(i);
}
vector<bool> koristen(n, false);
ll res = 0;
ll pocetak = n - 2;
for (int i = n - 1; i >= 0; i--){
if (koristen[i])
continue;
ll curr = i;
ll par;
if (s[i] < 0){
res++;
par = cnt1[-s[i]].front();
cnt1[-s[i]].pop();
cnt2[-s[i]].pop();
}
else{
par = cnt2[s[i]].front();
cnt1[s[i]].pop();
cnt2[s[i]].pop();
}
koristen[i] = true;
koristen[par] = true;
curr += getSum(curr);
par += getSum(par);
res += pocetak - par;
updateF(n, par + 1, -1);
pocetak -= 2;
}
return res;
}
