#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
int n = int(s.size()) / 2;
s.insert(s.begin(), 0);
vector<int> bit(n+n+1, 0), a(n+n+1, 0);
vector<int> b(1);
for (int i = 1; i <= n+n; i++) {
if (s[i] > 0) b.emplace_back(s[i]);
}
sort(b.begin()+1, b.end());
for (int i = 1; i <= n+n; i++) {
if (s[i] > 0) {
s[i] = lower_bound(b.begin()+1, b.end(), s[i]) - b.begin();
} else s[i] = -(lower_bound(b.begin()+1, b.end(), -s[i]) - b.begin());
}
function<void(int, int)> upd = [&](int u, int d) {
for (int i = u; i > 0; i -= i & -i) bit[i] += d;
};
function<int(int)> get = [&](int u) {
int kq = 0;
for (int i = u; i <= n+n; i += i & -i) kq += bit[i];
return kq;
};
vector<vector<int> > nho(n+1, vector<int>(0));
int cnt = 0;
for (int i = 1; i <= n+n; i++) {
if (s[i]<0) {
++cnt;
a[i] = cnt*2-1;
nho[-s[i]].emplace_back(a[i]+1);
}
}
for (int i = 1; i <= n; i++) reverse(nho[i].begin(), nho[i].end());
for (int i = 1; i <= n+n; i++) {
if (s[i]<0) continue;
a[i] = nho[s[i]].back();
nho[s[i]].pop_back();
}
long long kq = 0;
for (int i = 1; i <= n+n; i++) {
kq += get(a[i]);
upd(a[i], 1);
}
return kq;
}
