#include <bits/stdc++.h>
// #include "shoes.h"
using namespace std;
using ll = long long;
ll cntAndMerge(vector<ll>& A, ll l, ll m, ll r) {
ll nLeft = m - l + 1, nRight = r - m;
vector<ll> L(nLeft), R(nRight);
for (ll i = 0; i < nLeft; i++) {
L[i] = A[i + l];
}
for (ll j = 0; j < nRight; j++) {
R[j] = A[m + 1 + j];
}
ll res = 0;
ll i = 0, j = 0, k = l;
while (i < nLeft && j < nRight) {
if (L[i] <= R[j]) {
A[k] = L[i];
k++; i++;
} else {
A[k] = R[j];
k++; j++;
res += nLeft - i;
}
}
while (i < nLeft) {
A[k] = L[i];
k++; i++;
}
while (j < nRight) {
A[k] = R[j];
k++; j++;
}
return res;
}
ll cntInversions(vector<ll>& arr, ll l, ll r) {
ll res = 0;
if (l < r) {
ll m = (r + l) / 2;
res += cntInversions(arr, l, m);
res += cntInversions(arr, m + 1, r);
res += cntAndMerge(arr, l, m, r);
}
return res;
}
ll inversionCount(vector<ll> &arr) {
ll N = arr.size();
return cntInversions(arr, 0, N - 1);
}
ll count_swaps(vector<int> shoes) {
ll N = shoes.size() / 2;
// {index, isNegative}
map<ll, priority_queue<ll, vector<ll>, greater<ll> > > mapOfPQs;
map<ll, queue<ll> > mapOfStack;
for (ll i = 0; i < 2 * N; i++) {
mapOfPQs[shoes[i]].push(i);
mapOfStack[shoes[i]].push(i);
}
vector<ll> supposedPosition;
vector<bool> alreadyConsidered(2 * N, false);
supposedPosition.reserve(2*N);
for (ll i = 0; i < 2 * N; i++) { // just place them where they're meant to be
if (alreadyConsidered[i]) continue;
ll firstPosition = mapOfPQs[shoes[i]].top();
mapOfPQs[shoes[i]].pop();
ll secondPosition = mapOfPQs[-shoes[i]].top();
mapOfPQs[-shoes[i]].pop();
supposedPosition.push_back(shoes[i]);
supposedPosition.push_back(-shoes[i]);
alreadyConsidered[firstPosition] = true;
alreadyConsidered[secondPosition] = true;
}
vector<ll> meantToBe(2 * N);
for (ll i = 0; i < 2 * N; i++) {
meantToBe[i] = mapOfStack[supposedPosition[i]].front();
mapOfStack[supposedPosition[i]].pop();
}
// did not care about negative/positive until now
ll extraMoves = 0;
for (ll i = 0; i < 2 * N; i+=2) {
if (supposedPosition[i] > supposedPosition[i + 1]) {
extraMoves++;
}
}
return inversionCount(meantToBe) + extraMoves;
}
