#include "shoes.h"
#include <vector>
#include <algorithm>
#pragma GCC optimize("O2")
using namespace std;
vector<int> t;
void update(int v, int tl, int tr, int pos)
{
if(tl == tr)
++t[v];
else
{
int mid = (tl + tr)/2;
if(pos <= mid)
update(v*2, tl, mid, pos);
else
update(v*2+1, mid+1, tr, pos);
t[v] = t[v*2] + t[v*2+1];
}
}
int query(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 query(v*2, tl, mid, l, min(mid, r)) +
query(v*2+1, mid+1, tr, max(mid+1, l), r);
}
long long count_swaps(std::vector<int> s)
{
int n = s.size();
t.resize(4*n);
vector<vector<int>> l(n), r(n);
for(int i = 0; i < n; ++i)
if(s[i] < 0)
l[-s[i]-1].push_back(i);
else
r[s[i]-1].push_back(i);
long long ans = 0;
vector<char> used(n);
vector<int> cnt(n);
for(int i = 0; i < n; ++i)
{
if(used[i])
continue;
if(s[i] < 0)
{
ans += r[-s[i]-1][cnt[-s[i]-1]] - i - query(1, 0, n-1, i, r[-s[i]-1][cnt[-s[i]-1]]) - 1;
used[r[-s[i]-1][cnt[-s[i]-1]]] = 1;
update(1, 0, n-1, r[-s[i]-1][cnt[-s[i]-1]]);
}
else
{
ans += l[s[i]-1][cnt[s[i]-1]] - i - query(1, 0, n-1, i, l[s[i]-1][cnt[s[i]-1]]);
used[l[s[i]-1][cnt[s[i]-1]]] = 1;
update(1, 0, n-1, l[s[i]-1][cnt[s[i]-1]]);
}
++cnt[abs(s[i])-1];
}
return ans;
}
