#include "shoes.h"
using namespace std;
#define MAXN 100000
#define MAXN2 200000
int a[MAXN2];
int shoes[MAXN2];
int index[MAXN2 + 1];
int cnt[MAXN], cntl[MAXN];
int N, N2;
void clear_array(int *ar, int n) {
for (register int i = 0; i < n; i++)
ar[i] = 0;
}
void copy_arr(int *a1, vector <int> a2, int n) {
for (int i = 0; i < n; i++)
a1[i] = a2[i];
}
class BIT
{
int count(int right)
{
register int cnt = 0;
for (; right >= 0; right = (right & (right + 1)) - 1)
{
cnt += a[right];
}
return cnt;
}
public:
BIT()
{
clear_array(a, 2 * N);
}
int count(int left, int right)
{
return count(right) - count(left - 1);
}
void insert(int index)
{
for (; index < N2; index = index | (index + 1))
{
a[index]++;
}
}
};
void create_index()
{
clear_array(index, N2 + 1);
for (register int i = 0; i < N2; i++)
{
index[shoes[i] + N] = i;
}
}
void convert() {
clear_array(cnt, N);
for (int i = 0; i < N2; i++)
if (shoes[i] > 0)
cnt[shoes[i] - 1]++;
for (int i = 1; i < N; i++) {
cnt[i] += cnt[i - 1];
cntl[i] = cnt[i];
}
cntl[0] = cnt[0];
for (int i = 0; i < N2; i++)
if (shoes[i] > 0)
shoes[i] = (--cntl[shoes[i] - 1]) + 1;
else
shoes[i] = -((--cnt[-shoes[i] - 1]) + 1);
}
long long count_swaps(vector<int> S)
{
N = S.size() / 2;
N2 = 2 * N;
copy_arr(shoes, S, 2 * N);
convert();
create_index();
BIT tree = BIT();
long long ans = 0;
for (int i = 0; i < N2; i++)
{
if (shoes[i] != 0)
{
int pos = index[-shoes[i] + N];
ans += pos - i - tree.count(i, pos) - (shoes[i] < 0 ? 1 : 0);
shoes[pos] = 0;
tree.insert(pos);
}
}
return ans;
}
