#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define itr(a) a.begin(), a.end()
typedef vector<int> vi;
typedef unordered_map<int, int> mii;
void build(vector<int> &t, vector<int> arr, int v, int l, int r)
{
if (l == r)
{
t[l] = 0;
}
else
{
int mid = (l + r) / 2;
build(t, arr, v * 2, l, mid);
build(t, arr, v * 2 + 1, mid + 1, r);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
int sum(vector<int> t, int v, int tl, int tr, int l, int r)
{
if (l > r)
return 0;
if (tl == l && tr == r)
return t[v];
int mid = (tl + tr) / 2;
return sum(t, v * 2, tl, mid, l, min(r, mid)) + sum(t, v * 2 + 1, mid + 1, tr, max(l, mid + 1), r);
}
void update(vector<int> &t, int v, int l, int r, int i, int V)
{
if (l == r)
{
t[i] += V;
}
else
{
int mid = (l + r) / 2;
if (i <= mid)
update(t, v * 2, l, mid, i, V);
else
update(t, v * 2 + 1, mid + 1, r, i, V);
t[v] = t[v * 2] + t[v * 2 + 1];
}
}
long long count_swaps(vi s)
{
int n = s.size(), l = 0;
long long c = 0;
mii chain, rev;
vector<int> t(n * 4);
unordered_map<int, queue<int>> ref;
build(t, s, 1, 0, n - 1);
for (int i = 0; i < n; i++)
{
ref[s[i]].push(i);
}
for (int i = 0; i < n / 2; i++)
{
int ln = s[l], li = l;
li = ref[-ln].front();
ref[ln].pop();
ref[-ln].pop();
c += li - l - sum(t, 1, 0, n - 1, l, li) - (ln < 0);
update(t, 1, 0, n - 1, li, 1);
if (l + 1 == li)
l += 2;
else
l += 1;
}
return c;
}
