/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
ll count_swaps (vector <int> s)
{
int n = (int) s.size() / 2;
{
vector <vector <int>> l (n);
vector <vector <int>> r (n);
for(int i = 0; i < n * 2; i++)
{
int x = abs(s[i]) - 1;
if(s[i] < 0)
l[x].push_back(i);
else
r[x].push_back(i);
}
int curr = 0;
for(int x = 0; x < n; x++)
{
sort(l[x].begin(), l[x].end());
sort(r[x].begin(), r[x].end());
for(int i = 0; i < (int) l[x].size(); i++)
{
curr++;
s[l[x][i]] = -curr;
s[r[x][i]] = curr;
}
}
}
vector <int> first (n, -1);
vector <ll> BIT (n * 2, 0);
function <void (int)> update = [&] (int pos)
{
pos++;
for(int i = pos; i <= n * 2; i += i & -i)
BIT[i - 1]++;
};
function <ll (int)> query = [&] (int pos)
{
pos++;
ll sum = 0;
for(int i = pos; i >= 1; i -= i & -i)
sum += BIT[i - 1];
return sum;
};
ll answer = 0;
for(int i = 0; i < n * 2; i++)
{
int x = abs(s[i]) - 1;
if(first[x] == -1)
{
first[x] = i;
update(first[x]);
if(s[i] > 0)
answer++;
}
else
{
answer += query(i) - query(first[x]);
update(first[x]);
}
}
return answer;
}
