#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
long long count_swaps(std::vector<int> a) {
int n = a.size();
map<int, vector<int>> pos;
for (int i = 0; i < n; i++) {
pos[a[i]].push_back(i);
}
vector<int> best(n, -1);
for (int i = n - 1; i >= 0; i--) {
if (a[i] == 0 or pos[-a[i]].size() == 0) {
continue;
}
best[i] = pos[-a[i]].back();
a[best[i]] = 0;
pos[-a[i]].pop_back();
pos[a[i]].pop_back();
}
int sz = 0;
int ans = 0;
ordered_set st;
for (int i = n - 1; i >= 1; i--) {
if (best[i] == -1) continue;
while (st.size() and *st.find_by_order(st.size() - 1) >= i) {
st.erase(st.find_by_order(st.size() - 1));
}
int cur = i - best[i];
if (st.size() != 0) {
int j = -1;
int l = 0, r = st.size() - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (*st.find_by_order(mid) <= best[i]) {
l = mid + 1;
} else {
j = mid;
r = mid - 1;
}
}
if (j != -1) cur -= st.size() - j;
}
ans += cur;
if (a[i] > 0) {
ans -= 1;
}
st.insert(best[i]);
}
return ans;
}
