#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; int tree[200200]; void update(int i, int val) { for(; i < 200200; i += -i&i) { tree[i] += val; } } int get(int x) { int ans = 0; for(; x; ans += tree[x], x ^= -x&x); return ans; } queue < int > q[100100]; ll count_swaps(vector< int > s) { int n = s.size(); ll ans = 0; for(int i = 0, j; i < n; ++ i) { j = abs(s[i]); if(q[j].empty() || s[q[j].front()] == s[i]) { q[j].push(i); } else { ans += i - (q[j].front() + get(q[j].front() + 1)) - (s[i] > 0); update(q[j].front() + 1, 1); update(i + 1, -1); q[j].pop(); } } return ans; }