#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
int count_swaps(vi32 s)
{
int n = sz(s);
vb vis(n);
vi freeSpaces(n);
map<int, vi> ixs;
rev(n, i)
{
ixs[s[i]].pb(i);
}
auto rSum = [&](int l, int r) -> int
{
int res = 0;
for (int i = l; i <= r; i++)
res += freeSpaces[i];
return res;
};
int res = 0;
loop(n, i)
{
if (!vis[i])
{
int vl = s[i];
int nxt = ixs[-vl].back();
ixs[-vl].pop_back();
res += (nxt - i - 1 - rSum(i + 1, nxt - 1));
if (vl > 0)
res++;
vis[nxt] = 1;
freeSpaces[nxt] = 1;
ixs[vl].pop_back();
}
}
return res;
}
