#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>;
const int MXN = 1e5 + 5;
int segtree[MXN << 2];
void update(const int &v, const int &tl, const int &tr, const int &pos, const int &val) {
if (tl == tr) {
segtree[v] = val;
return;
}
int tm = (tl + tr) >> 1;
if (pos > tm) update(v << 1 | 1, tm + 1, tr, pos, val);
else update(v << 1, tl, tm, pos, val);
segtree[v] = segtree[v << 1] + segtree[v << 1 | 1];
}
int getans(const int &v, const int &tl, const int &tr, const int &l, const int &r) {
if (l > r || tl > r || l > tr) return 0;
if (l <= tl && tr <= r) return segtree[v];
int tm = (tl + tr) >> 1;
return getans(v << 1, tl, tm, l, min(r, tm)) + getans(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r);
}
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) + 1);
else if (it1 != S.end()) res -= (int)S.size() - S.order_of_key(*it1);
S.insert({ri, i});
total += res, i++;
}
return total;
}
