#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
const int Mx = 200005;
int arr[Mx];
int used[Mx];
//fenwick tree functions
void add(int index, int x) {
index++;
while (index < Mx) {
arr[index] += x;
index += index & -index;
}
}
int get(int index) {
index++;
int r = 0;
while (index > 0) {
r += arr[index];
index -= index & -index;
}
return r;
}
long long count_swaps(std::vector<int> s) {
//build the trees
int n = s.size() / 2;
queue<int> right[n+1], left[n+1];
for (int i = 0; i < n*2; i++) {
if (s[i] > 0) right[s[i]].push(i+1);
else left[-s[i]].push(i+1);
}
//same idea as before, go through, but with fenwick
long long ans = 0;
for (int i = 0; i < n*2; i++) {
if (used[i+1]) continue;
int x = right[abs(s[i])].front();
int y = left[abs(s[i])].front();
right[abs(s[i])].pop();
left[abs(s[i])].pop();
if (s[i] > 0) {
ans += y - x - (get(y) - get(x));
add(y, 1);
} else {
ans += x - y - (get(x) - get(y)) - 1;
add(x, 1);
}
used[y] = 1;
used[x] = 1;
}
return ans;
}
