#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<ll> tree;
int treeSize;
int pot(int x){
int tmp = 1;
while(x){
x/=2;
tmp*=2;
}
return tmp;
}
void update(int a){
a+=treeSize;
while(a){
tree[a]++;
a/=2;
}
}
int qur(int a, int b){
a+=treeSize;
b+=treeSize;
int out = tree[a];
if(b!=a) out+=tree[b];
while(a/2!=b/2){
if(a%2==0) out+=tree[a+1];
if(b%2==1) out+=tree[b-1];
a/=2;
b/=2;
}
return out;
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector<queue<int>> tab(n+10);
vector<int> ile(n+10);
vector<int> ile2(n+10);
treeSize = pot(n+3);
tree.resize(treeSize*2+1);
ll wyn = 0;
for(int i = 0; i < (int)s.size(); i++){
if(s[i]<0){
if(ile2[-s[i]]>0){
ile2[-s[i]]--;
tab[-s[i]].push(i);
s[i] = -s[i];
}else{
ile[-s[i]]++;
}
}else{
if(ile[s[i]]==0){
wyn++;
ile2[s[i]]++;
s[i] = -s[i];
}else{
tab[s[i]].push(i);
ile[s[i]]--;
}
}
}
for(int i = 0; i < (int)s.size(); i++){
if(s[i]<0){
int x = tab[-s[i]].front();
tab[-s[i]].pop();
wyn+=x-i-1;
wyn-=qur(i, x);
update(x);
}
}
return wyn;
}
