#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll = long long;
int sgn(int x) {
if (x == 0) return 0;
return x > 0 ? 1 : -1;
}
ll count_inversions(vector<int>& v, int l, int r) {
if (r - l == 1) return 0;
int mid = (l + r) / 2;
ll ans = count_inversions(v, l, mid) + count_inversions(v, mid, r);
int l_ptr = l, r_ptr = mid;
vector<int> m;
m.reserve(r - l);
while (l_ptr < mid || r_ptr < r) {
if (l_ptr == mid) {
m.push_back(v[r_ptr++]);
} else if (r_ptr == r) {
ans += r_ptr - mid;
m.push_back(v[l_ptr++]);
} else if (v[l_ptr] <= v[r_ptr]) {
ans += r_ptr - mid;
m.push_back(v[l_ptr++]);
} else {
m.push_back(v[r_ptr++]);
}
}
copy(m.begin(), m.end(), v.begin() + l);
return ans;
}
ll count_swaps(vector<int> s) {
int n = s.size() / 2;
vector<int> v {0};
for (int x : s) {
if (x > 0) v.push_back(x);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i < 2 * n; ++i) {
int k = sgn(s[i]);
s[i] = k * (lower_bound(v.begin(), v.end(), abs(s[i])) - v.begin());
}
vector<int> t;
vector<int> cnt(v.size());
for (int i = 0; i < 2 * n; ++i) {
int sz = abs(s[i]);
if (cnt[sz] == 0 || sgn(s[i]) == sgn(cnt[sz])) {
t.push_back(-sz);
t.push_back(sz);
}
cnt[sz] += sgn(s[i]);
}
int offset = v.size() - 1;
vector<stack<int>> st(2 * v.size() - 1);
for (int i = 2 * n - 1; i >= 0; --i) {
st[s[i] + offset].push(i);
}
vector<int> perm(2 * n);
for (int i = 0; i < 2 * n; ++i) {
perm[i] = st[t[i] + offset].top();
st[t[i] + offset].pop();
}
return count_inversions(perm, 0, 2 * n);
}
