#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
bool visit[200011] = {};
long long n, ret = 0, bit[200011] = {}, s[200011], ans[200011];
queue<int> Left[100006], Right[100006];
void bld(void)
{
for (int i = 2; i <= n + 10; i++)
bit[i] = i - max(1, i - (i & -i));
}
long long sum(int x)
{
long long ret = 0;
for (int i = x; i >= 1; i -= (i & -i))
ret += bit[i];
return ret;
}
void edt(int x, int k)
{
for (int i = x; i <= n; i += (i & -i))
bit[i] -= k;
}
long long count_swaps(vector<int> in)
{
n = in.size();
s[0] = 0;
for (int i = 1; i <= n; i++)
{
s[i] = in[i - 1];
if (s[i] < 0)
Left[-s[i]].push(i);
else
Right[s[i]].push(i);
}
bld();
int cnt = 0, pos, tar;
for (int i = 1; i <= n; i++)
{
if (visit[i])
continue;
tar = -abs(s[i]);
pos = Left[-tar].front(), Left[-tar].pop();
ans[cnt++] = tar;
visit[pos] = true;
ret += sum(pos);
edt(pos, 1);
tar = -ans[cnt - 1];
pos = Right[tar].front(), Right[tar].pop();
ans[cnt++] = tar;
visit[pos] = true;
ret += sum(pos);
edt(pos, 1);
}
return ret;
}
