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