#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
struct fenwick {
int n; vector<int> bit;
fenwick(int a) : n(a), bit(a+1) {}
void update(int pos, int x) {
pos++;
for (int i = pos; i <= n; i += i&-i) bit[i] += x;
}
int sum(int pos) {
int res = 0;
while (pos) res += bit[pos], pos -= pos&-pos;
return res;
}
int query(int l, int r) {
return sum(r+1) - sum(l);
}
};
long long count_swaps(std::vector<int> s) {
int n = sz(s);
vector<bool> vis(n);
ll ans = 0;
map<int, vector<int>> mp;
for (int i = 0; i < n; i++) {
mp[s[i]].emplace_back(i);
}
for (auto &[x, y] : mp) reverse(all(y));
fenwick fw(n);
for (int i = 0; i < n; i++) if (!vis[i]) {
int pos = mp[-s[i]].back();
mp[s[i]].pop_back();
mp[-s[i]].pop_back();
assert(pos >= i);
ans += pos - i - (s[i] < 0) - fw.query(i, pos);
fw.update(pos, 1);
vis[i] = 1, vis[pos] = 1;
}
return ans;
}
