#include <bits/stdc++.h>
#include "shoes.h"
#define ll long long
//#include "grader.cpp"
using namespace std;
vector <int> v;
vector <ll> fenwick;
void update(ll idx)
{
for (int i = idx; i < (ll)fenwick.size(); i = (i | (i + 1)))
{
fenwick[i]++;
}
}
ll query(ll idx)
{
ll res = 0;
for (int i = idx; i >= 0; i = (i & (i + 1)) - 1)
{
res += fenwick[i];
}
return res;
}
ll query(ll a, ll b)
{
if (a > b) return 0;
if (a == 0) return query(b);
return query(b) - query(a - 1);
}
long long count_swaps(vector<int> s)
{
v = s;
ll n = v.size();
ll ptr = 0, ans = 0;
fenwick.assign(n + 2, 0);
map <ll, queue<ll>> mp;
for (int i = 0; i < n; i++)
{
mp[v[i]].push(i);
}
while (ptr < n)
{
if (query(ptr, ptr) == 1)
{
ptr++;
continue;
}
ll pos = mp[-v[ptr]].front();
mp[v[ptr]].pop();
mp[-v[ptr]].pop();
ll removed = query(ptr + 1, pos - 1);
ans += (pos - ptr - 1) - removed;
if (v[ptr] > 0) ans++;
update(pos);
ptr++;
}
return ans;
}
/*
2
2 1 -1 -2
4
3
-2 2 2 -2 -2 2
1
*/
