#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long count_swaps(vector<int> S) {
int n = S.size();long long ans = 0;
vector<int> bit(n + 1, 0);
auto up = [&](int i, int v){
for (; i <= n; i += i & -i) bit[i] += v;
};
auto qr = [&](int i){
int s = 0;
for(;i > 0; i -= i & -i) s += bit[i];
return s;
};
map<int, vector<int>> mp;
for(int i = n - 1; i >= 0; i--) mp[S[i]].push_back(i);
vector<int> v(n, 0);
for(int i = 0; i < n; i++) {
if(v[i]) continue; int x = S[i], j = mp[-x].back();
mp[x].pop_back(); mp[-x].pop_back();
v[j] = 1; ans += (j - i - (x < 0 ? 1 : 0) + qr(j + 1) - qr(i + 1));
up(i + 1, 1); up(j + 1, -1);
}
return ans;
}
