#include "shoes.h" #include<bits/stdc++.h> #define int long long using namespace std; int n, bit[200005]; void update(int p, int v) { for(int i = p; i <= n; i += i & (-i)) bit[i] += v; } int query(int p) { int ans = 0; for(int i = p; i > 0; i -= i & (-i)) ans += bit[i]; return ans; } bool used[200005]; int count_swaps(vector<int32_t> s) { memset(used, 0, sizeof(used)); n = s.size(); vector<list<int>> f(n+1); for(int i = 0; i < s.size(); i++) f[s[i]+n/2].push_back(i); int ans = 0; for(int i = 1; i <= n; i++) update(i, 1); for(int i = 0; i < n; i++) if(used[i] == 0){ used[i] = 1; int val = s[i]+n/2, target = -s[i]+n/2; f[val].pop_front(); int p = f[target].front(); f[target].pop_front(); used[p] = 1; update(i+1, -1); update(p+1, -1); ans += query(p+1); if(s[i] > 0 && s[p] < 0) ans++; //cerr<<"A"<<i<<" "<<p<<" "<<ans<<endl; } return ans; }