#include <bits/stdc++.h> using namespace std; #include "shoes.h" long long count_swaps(vector<int> A){ int n = A.size()/2,m = A.size(); long long res(0); vector<int> B(n,-1),segtree(2*m); vector C(n,queue<int>()); for (int i(0),k(1);i < m;++i) if (A[i]>0) C[A[i]-1].emplace(k),A[i] = k++; for (int i(0);i < m;++i) if (A[i]<0){ int t = C[abs(A[i])-1].front(); C[abs(A[i])-1].pop(),A[i] = -t; } for (int i(0);i < m;++i){ int x = abs(A[i])-1; if (B[x]==-1) B[x] = i; if (B[x]!=i){ for (int l(m+B[x]+1),r(m+i);l < r;l>>=1,r>>=1){ if (l&1) res += segtree[l++]; if (r&1) res += segtree[--r]; } res += (A[i]<0); } for (int l(m+B[x]);l;l>>=1) ++segtree[l]; } return res; }