#include "shoes.h"
#include <math.h>
#include <vector>
#include <map>
#include <iostream>
#include <stack>
#include <queue>
#include <bitset>
#include <unordered_map>
#include <chrono>
using namespace std;
#define endl '\n'
using ll = long long;
int const N = 1e5+10;
int si;
int fenwick[N];
bitset<N> used;
void update(int n, int val){
for(;n <= si;n += n&-n) fenwick[n] += val;
}
int sum(int n){
int sum = 0;
for(;n > 0;n -= n&-n) sum += fenwick[n];
return sum;
}
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector<vector<int>> mp(2*n+10);
vector<int> cur(2*n+10);
si = n;
for(int i{1};i <= n;i++){
fenwick[i] = i&-i;
}
for(int i{1};i <= n;i++){
mp[s[i-1]+n].emplace_back(i);
}
ll ans = 0;
for(int i{1};i <= n;i++){
if(used[i]) continue;
int tar = mp[-s[i-1]+n][cur[-s[i-1]+n]];
cur[-s[i-1]+n]++;
cur[s[i-1]+n]++;
used[tar] = 1;
used[i] = 1;
update(tar,-1);
update(i,-1);
ans += sum(tar)+(s[i-1]>0);
}
return ans;
}
