#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
using ll=long long;
long long brute(vector<int> &s){
ll ans=0;
for(int i=0;i<s.size();i+=2){
int mn;
for(int j=0;j<i;++j){
if(s[j]<0){
mn=j;
break;
}
}
for(int j=i;j<s.size();++j){
if(s[j]<0){
if(i-mn<j-i){
swap(s[mn],s[i]);
ans+=i-mn;
}
else{
swap(s[j],s[i]);
ans+=j-i;
}
break;
}
}
}
return ans;
}
long long count_swaps(std::vector<int> s) {
ll ans=0;
set<int> pos;
for(int i=0;i<s.size();++i){if(s[i]<0) pos.insert(i);}
for(int i=0;i<s.size();i+=2){
auto low=pos.lower_bound(i);
if(low==pos.begin()){
ans+=(*low-i);
pos.erase(low);
continue;
}
auto up=low--;
if(up==pos.end()||i-*low<*up-i){
ans+=(i-*low);
pos.erase(low);
continue;
}
ans+=(*up-i);
pos.erase(up);
}
assert(brute(s)==ans);
return ans;
}
