#include "shoes.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 1e5 + 5;
int t[4 * N];
int fix[N];
vector<vector<int>> v(N);
void update(int node, int tl, int tr, int pos) {
if (tl == tr) {
t[node]++;
return;
}
int mid = (tl + tr) / 2;
if (pos <= mid) {
update(node * 2, tl, mid, pos);
} else {
update(node * 2 + 1, mid + 1, tr, pos);
}
t[node] = t[node * 2] + t[node * 2 + 1];
}
int getsum(int node, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) {
return t[node];
}
int mid = (tl + tr) / 2;
return getsum(node * 2, tl, mid, l, min(r, mid)) +
getsum(node * 2 + 1, mid + 1, tr, max(mid + 1, l), r);
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
s.insert(s.begin(), 0);
for (int i = 1; i <= n; i++) {
s[i] += n / 2;
v[s[i]].pb(i);
}
long long op = 0;
for (int i = 1; i <= n; i++) {
if (fix[i]) continue;
int a = s[i];
int b = (a <= n / 2) ? a + n / 2 : a - n / 2;
int l = 0, r = v[b].size() - 1;
int ib = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (v[b][mid] > i) {
ib = v[b][mid];
r = mid - 1;
} else {
l = mid + 1;
}
}
int shift = getsum(1, 1, n, i + 1, ib - 1);
op += (ib - i - 1 - shift);
if (a > n / 2) op++;
update(1, 1, n, ib);
fix[ib] = 1;
}
return op;
}
