#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll ans = 0;
vector<int> arr;
int tree[808080];
void init(int v, int st, int ed) {
if (st == ed) {
tree[v] = 1;
return;
}
int mid = (st + ed) / 2;
init(2 * v, st, mid);
init(2 * v + 1, mid + 1, ed);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
void update(int v, int st, int ed, int idx) {
if (st > idx || ed < idx) return;
if (st == idx && ed == idx) {
tree[v] = 0;
return;
}
int mid = (st + ed) / 2;
update(2 * v, st, mid, idx);
update(2 * v + 1, mid + 1, ed, idx);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
int get(int v, int st, int ed, int lt, int rt) {
if (st > rt || lt > ed) return 0;
if (lt <= st && ed <= rt) return tree[v];
int mid = (st + ed) / 2;
return get(2 * v, st, mid, lt, rt) + get(2 * v + 1, mid + 1, ed, lt, rt);
}
deque<int> pdq[101010], mdq[101010];
long long count_swaps(std::vector<int> s) {
arr = s;
n = s.size()/2;
for (int i = 0; i < 2 * n; i++) {
if (s[i] > 0) pdq[s[i]].push_back(i);
if (s[i] < 0) mdq[-s[i]].push_back(i);
}
init(1, 0, 2*n-1);
for (int i = 0; i < 2 * n; i++) {
if (get(1, 0, 2*n-1, i, i) == 0) continue;
update(1, 0, 2*n-1, i);
if (s[i] > 0) {
pdq[s[i]].pop_front();
int j = mdq[s[i]].front();
mdq[s[i]].pop_front();
ans += get(1, 0, 2*n-1, i + 1, j - 1) + 1;
update(1, 0, 2*n-1, j);
}
if (s[i] < 0) {
mdq[-s[i]].pop_front();
int j = pdq[-s[i]].front();
pdq[-s[i]].pop_front();
ans += get(1, 0, 2*n-1, i + 1, j - 1);
update(1, 0, 2*n-1, j);
}
}
return ans;
}
