#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 2e5;
vector< vector< queue<int> > > pos(MAXN + 5, {{}, {}});
ll seg[MAXN * 4 + 5];
void update(int v, int tl, int tr, int l, int r, ll val)
{
if(l > r)
return;
if(l == tl && r == tr)
{
seg[v] += val;
} else
{
int tm = (tl + tr) / 2;
update(2 * v, tl, tm, l, min(tm, r), val);
update(2 * v + 1, tm + 1, tr, max(tm + 1, l), r, val);
}
}
ll get(int v, int tl, int tr, int pos)
{
if(tl == tr)
return seg[v];
int tm = (tl + tr) / 2;
if(pos <= tm)
return seg[v] + get(2 * v, tl, tm, pos);
else
return seg[v] + get(2 * v + 1, tm + 1, tr, pos);
}
// Moving elements cause some left elements to move right
long long count_swaps(std::vector<int> s) {
int n = s.size();
ll ans = 0;
//ll curr = 0;
for(int i = 0; i < n; i++)
{
if(s[i] < 0)
{
if(pos[abs(s[i])][0].size() > 0) // We have a right pair on our left.
{
ll temp = pos[abs(s[i])][0].front();
pos[abs(s[i])][0].pop();
int prev = temp;
temp += get(1, 0, 2 * n - 1, temp);
ans += i - temp; // 0 for reversing the pairs from RL to LR
//cout << ans << " " << temp << " " << prev << ' ' << i << "\n";;
update(1, 0, 2 * n - 1, prev, i, 1);
//cout << "hm\n";
} else
{
pos[abs(s[i])][1].push(i);
}
} else
{
if(pos[abs(s[i])][1].size() > 0) // We have a left pair on our left.
{
ll temp = pos[abs(s[i])][1].front();
pos[abs(s[i])][1].pop();
int prev = temp;
temp += get(1, 0, 2 * n - 1, temp);
ans += i - temp - 1; // -1 since not decrementing will cause it to have LR -> RL
update(1, 0, 2 * n - 1, prev, i, 1);
} else
{
pos[abs(s[i])][0].push(i);
}
}
//cout << i << "\n";
//curr++;
}
return ans;
}
