#include "shoes.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
typedef pair<int, int> pii;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
typedef tree<
pair<int, pii>,
null_type,
less<pair<int, pii>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
int count_swaps(vector<signed> s) {
int n = s.size();
map<int, int> m;
vector<pii> v(n);
FOR(i, n){
v[i] = {s[i], m[s[i]]};
m[s[i]]++;
}
ordered_set st;
map<pii, int> pos;
FOR(i, n){
st.insert({i, v[i]});
pos[v[i]] = i;
}
int res = 0;
FOR(i, n / 2){
pii cur = (*--st.end()).ss;
pii ot = {-cur.ff, cur.ss};
res += st.size() - st.order_of_key({pos[ot], ot}) - 2;
if(cur.ff < 0) res++;
st.erase(--st.end());
st.erase({pos[ot], ot});
/*
for (auto &j : st) {
cout << j.ff << " " << j.ss.ff << " " << j.ss.ss << " ";
}
cout << res << endl;
*/
}
return res;
}
