#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4e5 + 6e3;
map<int, vector<int>> mp;
int f[MAXN];
void add(int x, int y){
x++;
while (x < MAXN){
f[x] += y;
x += (-x & x);
}
}
void add(int l, int r, int y){
if (l > r) return;
add(l, y);
add(r + 1, -y);
}
int get(int x){
x++;
int sum = 0;
while (x > 0){
sum += f[x];
x -= (-x & x);
}
return sum;
}
int get(int l, int r){
return get(r) - get(l - 1);
}
long long count_swaps(vector<int> a) {
int n = a.size();
for (int i = 0; i < n; i++){
mp[a[i]].push_back(i);
}
vector<bool> used(n, false);
ll ans = 0;
for (int i = 0; i < n; i++){
if (used[i]) continue;
int j = i + get(i);
int l = 0, r = mp[-a[i]].size() - 1;
int ind = -1;
while (l <= r){
int mid = (l + r) >> 1;
int x = mp[-a[i]][mid];
if (x + get(x) > j){
ind = x;
r = mid - 1;
} else l = mid + 1;
}
//cout << i << ' ' << ind << ' ';
used[ind] = true;
ind += get(ind);
//cout << j << ' ' << ind << endl;
ans += ind - j - 1 + (a[i] > 0);
add(j + 1, ind - 1, 1);
}
return ans;
}
