#include <bits/stdc++.h>
#include "shoes.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
long long count_swaps(std::vector<int> s) {
int n = s.size();
ordered_set S;
set<int> W[n + 1];
vector<int> p(n + 1, 0);
for(int i = 0; i < n; i++){
p[i+1] = p[i];
if(s[i] > 0) S.insert(i), W[s[i]].insert(i);
else p[i+1]++;
}
long long cnt = 0;
for(int i = 0; i < n; i++){
if(s[i] > 0) continue;
cnt += S.order_of_key(i);
cnt += S.order_of_key(*W[-s[i]].begin());
cnt += max(0, p[*W[-s[i]].begin()+1] - p[i+1]);
S.erase(*W[-s[i]].begin());
W[-s[i]].erase(W[-s[i]].begin());
}
return cnt;
}
