#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;
// int n = s.size()/2;
// if (n == 0) return 0;
// // Compress
// set<int> visited;
// for (int i = 0; i < 2*n; i++) {
// visited.insert(abs(s[i]));
// }
// map<int, int> mapper;
// int idx = 1;
// for (auto x : visited) {
// mapper[x] = idx++;
// }
// for (int i = 0; i < 2*n; i++) {
// if (s[i] > 0) s[i] = mapper[s[i]];
// else s[i] = -mapper[-s[i]];
// }
// 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);
// }
// int curr = -1, calc = 1e7;
// for (int i = 1; i <= n; i++) {
// if (left[i].size() == 0) continue;
// int tmp = left[i][0]+right[i][0]-((left[i][0] < right[i][0])? 1 : 0);
// if (tmp < calc) {
// curr = i;
// calc = tmp;
// }
// }
// assert(curr != -1);
// vector<int> newS;
// for (int i = 0; i < 2*n; i++) {
// if (i == left[curr][0]) continue;
// if (i == right[curr][0]) continue;
// newS.push_back(s[i]);
// }
// return calc + count_swaps(newS);
}
