#include "shoes.h"
#include <algorithm>
typedef long long ll;
const int MAXM = 200005;
ll BIT[MAXM];
void add(int i, ll delta) {
while (i < MAXM) {
BIT[i] += delta;
i += (i & (-i));
}
}
ll query(int i) {
ll ans = 0;
while (i > 0) {
ans += BIT[i];
i -= (i & (-i));
}
return ans;
}
long long count_swaps(std::vector<int> s) {
int N = int(s.size()) / 2;
std::vector<int> loc[2*N+2];
for (int i = 0; i < 2*N; i++) {
int shoe = s[i];
if (shoe > 0) loc[shoe].push_back(i);
else loc[-shoe+(N+1)].push_back(i);
}
std::vector<std::pair<int, int>> sloc;
for (int i = 1; i <= N; i++) {
for (int idx = 0; idx < int(loc[i].size()); idx++) {
sloc.push_back({loc[i][idx] + loc[i+N+1][idx], i});
}
}
std::sort(sloc.begin(), sloc.end());
int perm[2*N];
int id[N+1];
for (int i = 0; i <= N; i++) {
id[i] = 0;
}
for (int i = 0; i < N; i++) {
int shoeid = sloc[i].second;
perm[loc[N+1+shoeid][id[shoeid]]] = 2*i;
perm[loc[shoeid][id[shoeid]]] = 2*i+1;
id[shoeid]++;
}
// count inversions
int M = 2 * N;
ll ans = 0;
for (int i = M-1; i >= 0; i--) {
ans += query(perm[i]+1);
add(perm[i]+1, 1);
}
return ans;
}
