#include "shoes.h"
#include "bits/stdc++.h"
using namespace std;
void update(int pos, int val, vector<int> &bit) {
++pos;
for (; pos < (int)bit.size(); pos += pos&-pos)
bit[pos] += val;
}
void range_update(int l, int r, int val, vector<int> &bit) {
update(l, val, bit);
update(r+1, val, bit);
}
int get(int pos, vector<int> &bit) {
++pos;
int res = 0;
for (; pos > 0; pos -= pos&-pos)
res += bit[pos];
return res;
}
long long count_swaps(vector<int> s) {
int n = (int)s.size() / 2;
long long ans = 0;
vector<int> bit(n+1, 0);
vector<vector<int>> l(n+1, vector<int>());
vector<queue<int>> r(n+1, queue<int>());
for (int i = 0; i < (int)s.size(); ++i) {
if (s[i] < 0) {
s[i] = -s[i];
if (r[s[i]].size()) {
ans += i - r[s[i]].front() - get(r[s[i]].front(), bit);
range_update(r[s[i]].front(), i, 1, bit);
r[s[i]].pop();
} else
l[s[i]].push_back(i);
} else {
if (l[s[i]].size()) {
ans += i - l[s[i]].back() - get(l[s[i]].back(), bit) - 1;
range_update(l[s[i]].front(), i, 1, bit);
l[s[i]].pop_back();
} else
r[s[i]].push(i);
}
}
return ans;
}
