#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int st[525000];
void add(int x, int xl, int xr, int p){
if(xl == xr){
if(xl == p) st[x]++;
return;
}
int mid = (xl + xr) / 2;
if(p <= mid) add(x * 2 + 1, xl, mid, p);
else add(x * 2 + 2, mid + 1, xr, p);
st[x] = st[x * 2 + 1] + st[x * 2 + 2];
return;
}
int sum(int x, int xl, int xr, int l, int r){
if(xl >= l && xr <= r) return st[x];
if(xr < l || xl > r) return 0;
int mid = (xl + xr) / 2;
return sum(x * 2 + 1, xl, mid, l, r) + sum(x * 2 + 2, mid + 1, xr, l, r);
}
long long count_swaps(vector<int> s) {
int n = s.size()/2;
map<int, priority_queue<int, vector<int>, greater<int>>> r, l;
for(int i = 0; i < 2 * n; i++){
if(s[i] > 0){
r[s[i]].push(i);
}else{
l[abs(s[i])].push(i);
}
}
vector<int> udh(2 * n, 0);
long long ans = 0;
for(int i = 0; i < 2*n; i++){
if(!udh[i]){
int pos;
if(s[i] > 0) pos = l[s[i]].top();
else pos=r[abs(s[i])].top();
l[abs(s[i])].pop();
r[abs(s[i])].pop();
ans += abs(i - pos) - 1;
ans -= sum(0, 0, 2 * n - 1, i + 1, pos);
if(s[i] > 0) ans++;
udh[pos] = 1;
add(0, 0, 2 * n - 1, pos);
}
}
return ans;
}
