#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct SegTree{
vector<int> e;
int size;
SegTree(int n){
size=1;
while(size<n) size<<=1;
e=vector<int>(2*size,0);};
void update(int v, int l, int r, int x, int y){
if (r<x||y<l) return;
if (l<=x&&y<=r){ e[v]++; return;}
int m=(l+r)/2;
update(2*v,l,m,x,y);
update(v*2+1,m+1,r,x,y);
}
int query(int v){
int ans=0;
v+=size-1;
while(v>0){
ans += e[v];
v/=2;
}
return ans;
}
};
long long count_swaps(std::vector<int> s) {
int n= s.size();
long long ans =0;
SegTree seg(n);
deque<int> shoes[n+1][2];
for(int i=0;i<n;i++){
int shoe=s[i];
int j=(int)(shoe>0);
shoes[shoe][j].push_back(i+1);
}
for(int i=0;i<n;i++){
int shoe=s[i];
int j=(int)(shoe>0);
if (shoes[shoe][j].front() == i+1){
int pos = shoes[shoe][1-j].front();
shoes[shoe][1-j].pop_front();
shoes[shoe][j].pop_front();
ans+=(pos+seg.query(pos))-(i+1+seg.query(i+1))-1;
ans+=j;
seg.update(1,1,n,i+1,pos);
}
}
return ans;
}
