#include <bits/stdc++.h>
#include "shoes.h"
using ll = long long;
using namespace std;
long long inversion_count(vector<int> v) {
ll ans = 0;
int n = v.size();
for(int& i : v)
i += 1;
int bit[n + 1]{};
for(int i = 0; i < n; ++i) {
assert(1 <= v[i] and v[i] <= n);
for(int idx = n; idx > 0; idx -= (idx&-idx)) {
ans += bit[idx];
}
for(int idx = v[i]; idx > 0; idx -= (idx&-idx)) {
ans -= bit[idx];
}
for(int idx = v[i]; idx <= n; idx += (idx&-idx)) {
bit[idx]++;
}
}
return ans;
}
long long count_swaps(std::vector<int> s) {
// ll ans = 0;
int n = (int)s.size() / 2;
vector<vector<int> > r(n + 1), l(n + 1);
for(int i = 0; i < 2*n; ++i) {
if(s[i] < 0) {
l[abs(s[i])].push_back(i);
}
else {
r[s[i]].push_back(i);
}
}
for(int i = 1; i <= n; ++i) {
reverse(l[i].begin(), l[i].end());
reverse(r[i].begin(), r[i].end());
}
vector<int> order(2*n, -1);
vector<bool> used(2*n, false);
int idx = 0;
for(int i = 0; i < 2*n; ++i) {
if(used[i]) {
continue;
}
const int sz = abs(s[i]);
int lshoe, rshoe;
if(s[i] < 0) {
lshoe = i;
rshoe = r[sz].back();
while(used[rshoe]) {
r[sz].pop_back();
rshoe = r[sz].back();
}
r[sz].pop_back();
}
else if(s[i] > 0) {
rshoe = i;
lshoe = l[sz].back();
while(used[lshoe]) {
l[sz].pop_back();
lshoe = l[sz].back();
}
l[sz].pop_back();
}
else assert(false);
assert(!used[lshoe] and !used[rshoe]);
assert(order[lshoe] == -1 and order[rshoe] == -1);
used[lshoe] = used[rshoe] = true;
order[lshoe] = idx;
order[rshoe] = idx+1;
idx += 2;
}
// for(int x : order)
// cout << x << ' ';
// cout << endl;
return inversion_count(order);
}
