#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
struct fenwick {
vector<int> tree;
int n;
void init(int len) {
n = len;
tree.assign(n + 1, 0);
}
void upd(int i, int v) {
for (i++; i <= n; i += i & (-i)) tree[i] += v;
}
int get(int i) {
int sum = 0;
for (i++; i > 0; i -= i & (-i)) sum += tree[i];
return sum;
}
int get(int l, int r) {
return get(r) - get(l - 1);
}
};
long long count_swaps(std::vector<int> s) {
map<int, queue<int>> mp;
vector<int> vec;
ll ans = 0;
fenwick fw; fw.init(s.size());
for (int i = 0; i < s.size(); i++) {
if (!mp[-s[i]].empty()) {
int j = mp[-s[i]].front(); mp[-s[i]].pop();
ans += fw.get(j + 1, s.size() - 1);
// cout << i << ' ' << j << ' ' << ans << endl;
if (s[i] < 0) ans++;
fw.upd(j, 1);
} else {
mp[s[i]].push(i);
fw.upd(i, 1);
}
}
// for (int x: vec) cout << x << ' ';
// cout << endl;
// for (int i = 1; i < vec.size(); i += 2) assert(vec[i] == -vec[i - 1]);
// for (int i = 1; i < vec.size(); i += 2) assert(min(vec[i], vec[i - 1]) == vec[i - 1]);
return ans;
}
