#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
struct SegTree {
vi st;
int n;
inline void merge(int p) {
st[p] = st[2*p] + st[2*p+1];
}
void build(int p, int l, int r) {
if (l == r) {
st[p] = 1;
}
else {
int m = (l+r)/2;
build(2*p, l, m);
build(2*p+1, m+1, r);
merge(p);
}
}
SegTree(int n_) {
n = n_;
st.resize(4*n);
build(1, 0, n-1);
}
int count(int p, int l, int r, int i, int j) {
if (r < i or l > j) return 0;
if (i <= l and r <= j) return st[p];
int m = (l+r)/2;
return count(2*p, l, m, i, j) + count(2*p+1, m+1, r, i, j);
}
void upd(int p, int l, int r, int i, int x) {
if (l == r) {
st[p] = x;
}
else {
int m = (l+r)/2;
if (i <= m)
upd(2*p, l, m, i, x);
else
upd(2*p+1, m+1, r, i, x);
merge(p);
}
}
void upd(int i, int x) { upd(1, 0, n-1, i, x); }
int count(int i, int j) { return count(1, 0, n-1, i, j); }
};
ll count_swaps(vi s) {
int n = s.size();
map<int,vi> m;
for (int i = 0; i < n; ++i) {
m[s[i]].push_back(i);
}
for (auto& it : m) {
reverse(it.second.begin(), it.second.end());
}
SegTree st(n);
ll cnt = 0;
for (int i = 0; i < n; ++i) {
if (st.count(i, i) == 1) {
int j = m[-s[i]].back();
m[-s[i]].pop_back();
cnt += st.count(i+1, j-1);
if (s[i] > 0) ++cnt;
st.upd(j, 0);
}
}
return cnt;
}
