#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int MX = 4E5;
vector<bool> paired(MX, false);
map<int, queue<int>> nxt;
vector<int> tree(4 * MX, 0);
void update(int l, int r, int x = 0, int lo = 0, int hi = MX - 1)
{
if (r < lo || l > hi || r < l)
return;
// cout << l << " " << r << " " << tree[x] << " \n";
if ((lo == l && hi == r))
{
tree[x]++;
return;
}
int mid = (lo + hi) / 2;
update(l, min(mid, r), 2 * x + 1, lo, mid);
update(max(l, mid + 1), r, 2 * x + 2, mid + 1, hi);
}
int query(int t, int x = 0, int lo = 0, int hi = MX - 1)
{
if (t < lo || t > hi)
return 0;
if (lo == hi && lo == t)
{
return tree[x];
}
int mid = (lo + hi) / 2;
return query(t, 2 * x + 1, lo, mid) + query(t, 2 * x + 2, mid + 1, hi) + tree[x];
}
long long count_swaps(std::vector<int> s)
{
long long N = s.size(), ans = 0;
for (int i = 0; i < N; i++)
{
nxt[s[i]].push(i);
}
for (int i = 0; i < N; i++)
{
if (paired[i])
continue;
int j = nxt[-s[i]].front();
nxt[-s[i]].pop();
nxt[s[i]].pop();
update(i + 1, j - 1);
// cout << i << " " << query(i) << " " << j << " " << query(j) << " " << s[i] << " " << s[j] << " " << ans << "\n";
ans += (j + query(j)) - (i + query(i)) - (s[i] < 0 ? 1 : 0);
paired[j] = true;
}
return ans;
}
