#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int tree[1000005];
int getLeft(int x){
return 2*x+1;
}
int getRight(int x){
return 2*x+2;
}
void update(int target, int il, int ir, int idx, int val){
if(il > ir || ir < target || il > target) return;
if(il == ir){
tree[idx] += val;
return;
}
int mid = il+(ir-il)/2;
update(target, il, mid, getLeft(idx), val);
update(target, mid+1, ir, getRight(idx), val);
tree[idx] = tree[getLeft(idx)]+tree[getRight(idx)];
}
int getVal(int left, int right, int il, int ir, int idx){
if(il > ir || ir < left || il > right) return 0;
if(il >= left && ir <= right){
return tree[idx];
}
int mid = il+(ir-il)/2;
return getVal(left, right, il, mid, getLeft(idx)) + getVal(left, right, mid+1, ir, getRight(idx));
}
long long count_swaps(vector<int> s) {
for(int i = 0; i < 1000005; i++) tree[i] = 0;
int n = s.size();
for(int i = 0; i < n; i++){
update(i, 0, n-1, 0, 1);
}
vector<vector<queue<int>>> prev(n+1, vector<queue<int>>(2));
int pos[n];
for(int i = 0; i < n; i++){
if(s[i] < 0){
if(!prev[-s[i]][0].empty()){
pos[prev[-s[i]][0].front()] = i;
pos[i] = -1;
prev[-s[i]][0].pop();
} else {
prev[-s[i]][1].push(i);
}
} else {
if(!prev[s[i]][1].empty()){
pos[prev[s[i]][1].front()] = i;
pos[i] = -1;
prev[s[i]][1].pop();
} else {
prev[s[i]][0].push(i);
}
}
}
long long ans = 0;
for(int i = 0; i < n; i++){
if(pos[i] == -1) continue;
if(s[i] < 0){
ans += getVal(i+1, pos[i]-1, 0, n-1, 0);
update(pos[i], 0, n-1, 0, -1);
} else {
ans += getVal(i+1, pos[i]-1, 0, n-1, 0)+1;
update(pos[i], 0, n-1, 0, -1);
}
}
return ans;
}
