#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 segment[4*N];
bitset<N> used(0);
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
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) {
unordered_map<int,queue<int>,custom_hash> 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;
}
