#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; //}