#include "shoes.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace __gnu_pbds;
using namespace std;
// ordered_set
template<class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
long long count_swaps(vector<int> s) {
int n = s.size();
map<int, deque<int>> id;
Tree<pair<int, int>> t;
for (int i = 0; i < n; i++) {
id[s[i]].push_back(i);
t.insert(make_pair(i, s[i]));
}
long long ans = 0;
for (int i = 0; i < n / 2; i++) {
auto j = t.find_by_order(0);
int p = -((*j).second);
int d = t.order_of_key(make_pair(id[p][0], p));
ans += d - (p > 0 ? 1 : 0);
t.erase(j);
t.erase(t.find(make_pair(id[p][0], p)));
id[p].pop_front();
id[-p].pop_front();
}
return ans;
}
