#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
long long count_swaps(std::vector<int> s) {
using ll = long long;
#define int ll
int N = s.size();
int tot = 0;
vector<bool> marked(N);
vector<int> last(N);
vector<int> FST(2 * N);
auto point_upd = [&](int p, int v) {
for (p += N; p > 0; p >>= 1) FST[p] += v;
};
auto range_qry = [&](int l, int r) {
int ans = 0;
for (l += N, r += N + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += FST[l++];
if (r & 1) ans += FST[--r];
}
return ans;
};
vector<vector<deque<int>>> hmm(2, vector<deque<int>>(N));
for (int i = 0; i < N; ++i) {
auto &pot = hmm[s[i] < 0][abs(s[i])];
if (!pot.empty()) {
last[i] = pot.front();
pot.pop_front();
}
else hmm[s[i] > 0][abs(s[i])].emplace_back(i);
}
for (int i = N-1; i >= 0; --i) {
if (marked[i]) continue;
marked[last[i]] = true;
int distance = i - last[i] - 1 + (s[i] < 0);
distance -= range_qry(last[i], i);
tot += distance;
point_upd(last[i], 1);
}
return tot;
}
