#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(4*100001, 0);
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);
}
}
void build(vector<ll> arr, ll n){
for (int i = 1; i <= n; i++)
t[i] = 0;
for (int i = 0; i < n; i++)
updateF(n, i, arr[i]);
}
ll count_swaps(vector<int> s){
int n = s.size()/2;
vector<ll> arr(2*n, 0);
build(arr, 2*n);
vector<queue<int>> cnt(2*n, queue<int> ());
queue<int> q;
vector<bool> koristen(2*n, false);
for (int i = 2*n - 1; i >= 0; i--){
if (!koristen[abs(s[i])]){
q.push(i);
koristen[abs(s[i])] = true;
}
else{
cnt[abs(s[i])].push((i + 1)*abs(s[i])/s[i]);
koristen[abs(s[i])] = false;
}
}
int res = 0;
int pocetak = 2*n - 1;
while(!q.empty()){
int curr = q.front();
int par = cnt[abs(s[curr])].front();
q.pop(); cnt[abs(s[curr])].pop();
if (par > 0)
res++;
else
par = -par;
par--;
par += getSum(par);
res += pocetak - par - 1;
updateF(2*n, par, -1);
pocetak -= 2;
}
return res;
}
