#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
long long count_swaps(vector<int> ar)
{
int n = ar.size();
ar.resize(n + 1);
for(int i = n - 1; i >= 0; i--)
ar[i + 1] = ar[i];
vector<int> freq(n);
vector<queue<int>> dis(n);
function<bool(int, int)> diffSign = [](int a, int b)
{
return ((a < 0 and b > 0) or (a > 0 and b < 0));
};
long long ans = 0;
vector<int> bit(n + 1, 0);
function<void(int, int)> update = [&](int pos, int val)
{
for(;pos <= n; pos += (pos & -pos))
bit[pos] += val;
};
function<int(int, int)> query = [&](int l, int r)
{
int Qans = 0;
for(int pos = r; pos > 0; pos -= (pos & -pos))
Qans += bit[pos];
for(int pos = l; pos > 0; pos -= (pos & -pos))
Qans -= bit[pos];
return Qans;
};
for(int i = 1; i <= n; i++)
update(i, 1);
for(int i = 1; i <= n; i++)
{
if(diffSign(freq[abs(ar[i])], ar[i]))
{
int temp = ar[i] < 0;
ar[i] = abs(ar[i]);
(freq[ar[i]] < 0 ? freq[ar[i]]++ : freq[ar[i]]--);
int last = dis[abs(ar[i])].front(); dis[abs(ar[i])].pop();
ans += query(last, i - 1) + temp;
update(i, -1);
update(last, 1);
}
else
{
( ar[i] < 0 ? freq[abs(ar[i])]-- : freq[abs(ar[i])]++);
ar[i] = abs(ar[i]);
dis[ar[i]].push(i);
}
}
return ans;
}
