#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
vector<int> t;
SegmentTree(int n) {
t = vector<int>(4*n);
}
void update(int v, int tl, int tr, int pos, int x) {
if (tl == tr) {
t[v] = x;
} else {
int tm = (tl+tr)/2;
if (pos <= tm)
update(2*v, tl, tm, pos, x);
else
update(2*v+1, tm+1, tr, pos, x);
t[v] = (t[2*v] + t[2*v+1]);
}
}
int get(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
else if (tl == l && r == tr) return t[v];
else {
int tm = (tl+tr)/2;
return (get(2*v, tl, tm, l, min(tm, r)) + get(2*v+1, tm+1, tr, max(l, tm+1), r));
}
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size()/2;
long long res = 0;
vector<vector<int>> left(n+1), right(n+1);
for (int i = 0; i < 2*n; i++) {
if (s[i] < 0) left[abs(s[i])].push_back(i);
else right[abs(s[i])].push_back(i);
}
vector<int> nxt(2*n, -1);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < left[i].size(); j++) {
if (left[i][j] > right[i][j]) {
s[left[i][j]] *= -1;
s[right[i][j]] *= -1;
res++;
nxt[right[i][j]] = left[i][j];
} else {
nxt[left[i][j]] = right[i][j];
}
}
}
SegmentTree tree(2*n);
for (int i = 0; i < 2*n; i++) {
tree.update(1, 0, 2*n-1, i, s[i]/abs(s[i]));
}
for (int i = 0; i < 2*n; i++) {
if (s[i] > 0) continue;
res += nxt[i]-i-1;
tree.update(1, 0, 2*n-1, i, 0);
tree.update(1, 0, 2*n-1, nxt[i], 0);
res -= tree.get(1, 0, 2*n-1, nxt[i]+1, 2*n-1);
}
return res;
}
