//#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
set<pair<ll, ll>> left_shoes;
ll n, now,idx, ans;
map<ll, set<ll>>i_r_shoes;
queue<pair<ll, ll>> q;
void shift() {
for(auto c : left_shoes) {
ll IDX = c.first;
if(now <= IDX && IDX <= idx) {
ans++;
q.push({IDX, c.second});
}
}
while(!q.empty()) {
ll a = q.front().first , b = q.front().second;
left_shoes.erase({a, b});
left_shoes.insert({a + 1, b});
q.pop();
}
for(auto &c : i_r_shoes) {
queue<ll> q_p;
for(ll d : c.second) {
if(now <= d && d <= idx) q_p.push(d), ans++;
}
while(!q_p.empty()) {
ll a = q_p.front();
//if(c.second.find(a) != c.second.end()) prllf("YES\n");
c.second.erase(a);
c.second.insert(a+1);
//prllf("now %d %d\n", c.first, a+1);
q_p.pop();
}
}
}
long long count_swaps(std::vector<int> s) {
n = s.size();
for(ll i = 0; i < n; i++) {
if(s[i] < 0) left_shoes.insert({i, s[i]});
else i_r_shoes[s[i]].insert(i);
}
while(!left_shoes.empty()) {
idx = (*left_shoes.begin()).first;
ll type = (*left_shoes.begin()).second;
left_shoes.erase({idx, type});
shift();
now++;
/*prllf("here --> %d %d \n", type, idx);
for(auto c : left_shoes) {
prllf("%d %d\n", c.second, c.first);
}
for(auto c : i_r_shoes) {
for(auto d : c.second)prllf("%d %d\n", c.first, d);
}
*/
idx = *i_r_shoes[-type].begin();
i_r_shoes[-type].erase(idx);
shift();
now++;/*
prllf("%d\n", ans);
for(auto c : left_shoes) {
prllf("%d %d\n", c.second, c.first);
}
for(auto c : i_r_shoes) {
for(auto d : c.second)prllf("%d %d\n", c.first, d);
}*/
}
return ans;
}
