#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;
vi tree;
int treeN = 1;
int query(int i, int l, int r, int ql, int qr, int v)
{
if (qr < l || r < ql)
return 0;
if (ql <= l && r <= qr)
{
if (v == 1)
tree[i] = 1;
return tree[i];
}
int m = (l + r) / 2;
int res = query(2 * i, l, m, ql, qr, v) +
query(2 * i + 1, m + 1, r, ql, qr, v);
tree[i] = tree[2 * i] + tree[2 * i + 1];
return res;
}
int count_swaps(vi32 s)
{
int n = sz(s);
while (treeN < n)
treeN *= 2;
tree = vi(treeN * 2);
vb vis(n);
map<int, vi> ixs;
rev(n, i)
{
ixs[s[i]].pb(i);
}
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 - query(1, 0, treeN - 1, i + 1, nxt, 0));
if (vl > 0)
res++;
vis[nxt] = 1;
query(1, 0, treeN - 1, nxt, nxt, 1);
ixs[vl].pop_back();
}
}
return res;
}
