#include "bits/stdc++.h" #include "shoes.h" // #include "grader.cpp" using namespace std; long long n, ans, fn[500005], vs[500005]; map <long long, set<long long>> vis; void upd(long long x) { for(; x <= 2 * n; x += (x & (-x))) { fn[x]++; } return; } long long find(long long x) { long long sum = 0; for(; x > 0; x -= (x & (-x))) { sum += fn[x]; } return sum; } long long count_swaps(vector<int> s) { n = (long long)s.size(); for(long long i = 0; i < n; i++) { vis[s[i]].insert(i); } for(long long i = 0; i < n; i++) { if(vs[i]) continue; long long p = *vis[(-1) * s[i]].begin(); long long x1 = find(p) - find(i - 1); upd(p); ans += (p - i - 1) - x1; vs[p] = 1; vis[-s[i]].erase(p); vis[s[i]].erase(i); if(s[i] > 0) ans++; } return ans; }