#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
vector<int> t;
void update(int id, int tl, int tr, int i, int v) {
if (tl == tr) {
t[id] = v;
return;
}
int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
if (i <= tm) {
update(x, tl, tm, i, v);
} else {
update(y, tm + 1, tr, i, v);
}
t[id] = t[x] + t[y];
}
int get(int id, int tl, int tr, int l, int r) {
if (r < tl || tr < l) return 0;
if (l <= tl && tr <= r) return t[id];
int x = 2 * id + 1, y = x + 1, tm = (tl + tr) / 2;
return get(x, tl, tm, l, r) + get(y, tm + 1, tr, l, r);
}
long long count_swaps(vector<int> a) {
int n = a.size();
t.resize(4 * n);
for (int i = 0; i < n; i++) {
update(0, 0, n - 1, i, 1);
}
map<int, set<int>> m;
for (int i = 0; i < n; i++) {
m[a[i]].insert(i);
}
long long ans = 0;
for (int i = 0; i < n; i++) {
auto it = m[-a[i]].upper_bound(i);
if (it == m[-a[i]].end()) {
continue;
}
if (get(0, 0, n - 1, i, i) == 0) {
continue;
}
int j = *it;
if (a[i] > a[j]) {
ans++;
}
ans += get(0, 0, n - 1, i + 1, j - 1);
update(0, 0, n - 1, j, 0);
m[-a[i]].erase(j);
}
return ans;
}
