/***
* Author by cpismayilmmdv985, aka void
* Created 09.04.2026
*
* ██╗ ██╗ ██████╗ ██╗██████╗
* ██║ ██║██╔═══██╗██║██╔══██╗
* ██║ ██║██║ ██║██║██║ ██║
* ╚██╗ ██╔╝██║ ██║██║██║ ██║
* ╚████╔╝ ╚██████╔╝██║██████╔╝
* ╚═══╝ ╚═════╝ ╚═╝╚═════╝
***/
#include "shoes.h"
#include "bits/stdc++.h"
#include "ext/pb_ds/tree_policy.hpp"
#include "ext/pb_ds/assoc_container.hpp"
using namespace __gnu_pbds;
using namespace std;
using ordered_set = tree<array<int, 2>, null_type,less<array<int, 2>>, rb_tree_tag,tree_order_statistics_node_update>;
long long count_swaps(vector<int> a) {
int N = (int)a.size() >> 1;
// 1 based indexed..
vector<int> A((N << 1) + 5), L, R; for (int i = 0; i < (N << 1); i++)
A[i + 1] = a[i];
auto isIn = [&](array<int, 2> x, array<int, 2> y) -> bool {
if (x[0] <= y[0] && y[0] <= x[1] && x[1] <= y[1]) return true;
swap(x, y);
if (x[0] <= y[0] && y[0] <= x[1] && x[1] <= y[1]) return true;
return false;
};
vector<int> match((N << 1) + 5, -1);
vector<queue<int>> que((N << 1) + 5);
for (int i = 1; i <= (N << 1); i++) {
int num = (A[i] > 0 ? A[i] : N + abs(A[i])), wanted = (A[i] > 0 ? A[i] + N : abs(A[i]));
if (!que[wanted].empty()) {
int j = que[wanted].front(); que[wanted].pop();
match[j] = i, match[i] = j;
} else {
que[num].push(i);
}
}
int64_t total = 0, res;
int i = 1;
vector<bool> used((N << 1) + 5);
ordered_set S;
while (i <= (N << 1)) {
if (used[i]) {
i++;
continue;
}
res = 0;
int li = i, ri = match[i];
// cerr << li << ' ' << ri << '\n';
used[li] = used[ri] = true;
if (A[li] < 0 && A[ri] > 0) res = ri - li - 1;
else res = ri - li;
auto it1 = S.upper_bound({li, -1}), it2 = S.upper_bound({ri, -1});
if (it2 != S.end()) res -= (S.order_of_key(*it2) - S.order_of_key(*it1));
else if (it1 != S.end()) res -= (int)S.size() - S.order_of_key(*it1);
S.insert({ri, i});
total += res, i++;
}
return total;
}
