#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct segtree {
int size = 1;
vector<int> sums;
void init(int n) {
while (size < n) {
size *= 2;
}
sums.assign(2 * size, 0);
}
void build(vector<int> &v, int x, int lx, int rx) {
if (rx - lx == 1) {
if (lx < v.size()) {
sums[x] = v[lx];
}
return;
}
int m = (lx + rx) / 2;
build(v, 2 * x + 1, lx, m);
build(v, 2 * x + 2, m, rx);
sums[x] = sums[2 * x + 2] + sums[2 * x + 1];
}
void build(vector<int> &v) {
build(v, 0, 0, size);
}
void set(int i, int v, int x, int lx, int rx) {
if (rx - lx == 1) {
sums[x] = v;
return;
}
int m = (lx + rx) / 2;
if (i < m) {
set(i, v, x * 2 + 1, lx, m);
} else {
set(i, v, x * 2 + 2, m, rx);
}
sums[x] = sums[x * 2 + 1] + sums[x * 2 + 2];
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
int sum (int l, int r, int x, int lx, int rx) {
if (rx <= l || r <= lx )return 0 ;
if (l <= lx && rx <= r) return sums[x];
int m = (rx + lx) / 2;
int n1 = sum(l, r, x * 2 + 1, lx, m );
int n2 = sum(l, r, x * 2 + 2, m, rx );
return n1 + n2;
}
int sum(int l, int r) {
return sum(l, r, 0, 0, size);
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size();
vector<set<int>> left(n + 1);
vector<set<int>> right(n + 1);
vector<int> vis(n);
for (int i = 0; i < n ; i++) {
if (s[i] < 0) {
left[abs(s[i])].insert(i);
} else {
right[abs(s[i])].insert(i);
}
}
segtree st;
st.init(n);
long long result = 0;
for (int i = 0; i < n; i++) {
if (vis[i]) continue;
if (s[i] < 0) {
auto it = right[abs(s[i])].lower_bound(i);
result += *it - i;
result--;
result -= st.sum(i, *it);
st.set(*it, 1);
vis[*it] = 1;
right[abs(s[i])].erase(it);
} else {
auto it = left[abs(s[i])].lower_bound(i);
result += *it - i;
result -= st.sum(i, *it);
st.set(*it, 1);
vis[*it] = 1;
left[abs(s[i])].erase(it);
}
}
return result;
}
