#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
const int N_MAX = 100000;
int A[2 * N_MAX + 2];
vector <int> Minus[N_MAX + 2], Plus[N_MAX + 2];
int nxt[2 * N_MAX + 2];
bool used[2 * N_MAX + 2];
int BIT[2 * N_MAX + 2];
void update(int pos, int val) {
for (int i = pos; i <= 2 * N_MAX; i += i & -i) {
BIT[i] += val;
}
}
int query(int pos) {
int answer = 0;
for (int i = pos; i >= 1; i -= i & -i) {
answer += BIT[i];
}
return answer;
}
ll count_swaps(vector <int> S) {
int N = (int) S.size() / 2;
for (int i = 1; i <= 2 * N; i++) {
A[i] = S[i - 1];
}
for (int i = 2 * N; i >= 1; i--) {
if (A[i] < 0) {
Minus[A[i] * -1].push_back(i);
} else {
Plus[A[i]].push_back(i);
}
}
for (int i = 1; i <= 2 * N; i++) {
if (used[i] == true) {
continue;
}
used[i] = true;
if (A[i] < 0) {
if (Plus[A[i] * -1].empty() == false) {
nxt[i] = Plus[A[i] * -1].back();
Plus[A[i] * -1].pop_back();
}
Minus[A[i] * -1].pop_back();
} else {
if (Minus[A[i]].empty() == false) {
nxt[i] = Minus[A[i]].back();
Minus[A[i]].pop_back();
}
Plus[A[i]].pop_back();
}
used[nxt[i]] = true;
}
for (int i = 1; i <= 2 * N; i++) {
used[i] = false;
}
ll answer = 0;
for (int i = 1; i <= 2 * N; i++) {
if (used[i] == false) {
int j = nxt[i];
int between = query(j - 1) - query(i);
int swaps = (j - i - 1) - between;
if (A[i] > 0) {
swaps++;
}
answer += swaps;
used[i] = true;
used[j] = true;
update(i, +1);
update(j, +1);
}
}
return answer;
}
