#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define eb emplace_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
struct FT {
vector<ll> s;
FT(int n) : s(n) {}
void update(int pos, ll dif) { // a[pos] += dif
for (; pos < sz(s); pos |= pos + 1) s[pos] += dif;
}
ll query(int pos) { // sum of values in [0, pos)
ll res = 0;
for (; pos > 0; pos &= pos - 1) res += s[pos-1];
return res;
}
};
ll count_swaps(vi s) {
int n = sz(s)/2;
vector<deque<int>> nxtR(n+1);
vector<deque<int>> nxtL(n+1);
rep(i,0,2*n) {
if(s[i] > 0) nxtR[s[i]].eb(i);
else nxtL[-s[i]].eb(i);
}
FT ft(2*n+1); // pos delta
rep(i,1,2*n+1) ft.update(i, 1);
ll ans = 0;
vi alive(2*n, 1);
auto mv = [&](int target, int i, int q) {
int pos = ft.query(i+1);
ans += pos - target;
ft.update(0, 1);
ft.update(i+1, -1);
alive[nxtL[q].front()] = 0;
alive[nxtR[q].front()] = 0;
nxtL[q].pop_front();
nxtR[q].pop_front();
};
int j = 0;
rep(i,0,n) {
while(alive[j] == 0) ++j;
int q = abs(s[j]);
if (s[j] < 0) // left shoe
mv(2*i+1, nxtR[q].front(), q);
if (s[j] > 0) // right shoe
mv(2*i, nxtL[q].front(), q);
}
return ans;
}
