#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N = 1e5 + 10;
int st[8 * N];
void update(int index, int l, int r, int pos) {
if(l > r || pos < l || r < pos) return;
if(l == r) {
st[index]++;
return;
}
if(l <= pos && pos <= r) st[index]++;
int mid = (l + r) / 2;
update(2 * index + 1, l, mid, pos);
update(2 * index + 2, mid + 1, r, pos);
st[index] = st[2 * index + 1] + st[2 * index + 2];
}
int get(int index, int l, int r, int L, int R) {
if(l > r || R < l || r < L) return 0;
if(L <= l && r <= R) return st[index];
int mid = (l + r) / 2;
return get(2 * index + 1, l, mid, L, R) + get(2 * index + 2, mid + 1, r, L, R);
}
long long count_swaps(vector<int> a) {
int n = a.size();
long long res = 0;
vector<int> right[n / 2 + 1];
for(int i = 0; i < n; i++) if(a[i] > 0) right[a[i]].push_back(i);
vector<int> ll(n), rr(n);
vector<int> cnt(n / 2 + 1, 0);
for(int i = 0; i < n; i++) {
if(a[i] < 0) {
if(i < right[-a[i]][cnt[-a[i]]]) {
ll[i] = i;
rr[i] = right[-a[i]][cnt[-a[i]]];
ll[right[-a[i]][cnt[-a[i]]]] = i;
rr[right[-a[i]][cnt[-a[i]]]] = right[-a[i]][cnt[-a[i]]];
cnt[-a[i]]++;
} else {
res++;
swap(a[i], a[right[-a[i]][cnt[-a[i]]]]);
ll[right[a[i]][cnt[a[i]]]] = right[a[i]][cnt[a[i]]];
rr[right[a[i]][cnt[a[i]]]] = i;
ll[i] = right[a[i]][cnt[a[i]]];
rr[i] = i;
cnt[a[i]]++;
}
}
}
for(int i = 0; i < n; i++) {
if(rr[i] == i) {
res += get(0, 0, n - 1, ll[i], rr[i]);
update(0, 0, n - 1, ll[i]);
update(0, 0, n - 1, rr[i]);
}
}
return res;
}
