#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sum(vector<ll>& fenw, ll x) {
ll res = 0;
while (x > 0) {
res += fenw[x];
x -= (x&(-x));
}
return res;
}
void add(vector<ll>& fenw, ll x, ll k) {
while (x < fenw.size()) {
fenw[x] += k;
x += (x&(-x));
}
}
long long count_swaps(std::vector<int> s) {
ll n = s.size();
map<ll, pair<vector<ll>, ll>> mp;
for (ll i = 0; i < n; i++) {
mp[s[i]].first.push_back(i);
mp[s[i]].second = 0;
}
vector<ll> fenw(n+1, 0);
for (ll i = 1; i < n+1; i++) {
add(fenw, i, 1);
}
ll ans = 0;
set<ll> st;
for (ll i = 0; i < n; i++) {
if (st.count(i)) continue;
ll i2 = mp[-s[i]].first[mp[-s[i]].second];
ans += sum(fenw, i2)-sum(fenw, i+1);
if (s[i] > 0) ans++;
add(fenw, i+1, -1);
add(fenw, i2+1, -1);
mp[-s[i]].second++;
mp[s[i]].second++;
st.insert(i);
st.insert(i2);
}
return ans;
}
//int main() {
// cout << count_swaps({-2, 2, 2, -2, -2, 2}) << endl;
//}
