#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;
bool visit[200000] = {};
long long n, ret = 0, bit[200001] = {}, s[200001], ans[200001];
queue<int> Left[100001], Right[100001];
void bld(void)
{
for (int i = 1; i <= n + 10; i++)
for (int j = i; j > i - (i & -i); j--)
if (j != 1)
bit[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;
}
