#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <class T1, // answer value stored on nodes
class T2, // lazy update value stored on nodes
T1 merge(T1, T1),
void pushUpd(T2 & /*padre*/, T2 & /*hijo*/, int, int, int,
int), // push update value from a node to another.
// parent -> child
void applyUpd(T2 &, T1 &, int,
int) // apply the update value of a node to its answer
// value. upd -> ans
>
struct SegmentTreeLazy {
vector<T1> ST;
vector<T2> lazy;
vector<bool> upd;
int n;
void build(int i, int l, int r, vector<T1> &values) {
if (l == r) {
ST[i] = values[l];
return;
}
build(i << 1, l, (l + r) >> 1, values);
build(i << 1 | 1, (l + r) / 2 + 1, r, values);
ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
}
SegmentTreeLazy(vector<T1> &values) {
n = values.size();
ST.resize(n << 2 | 3);
lazy.resize(n << 2 | 3);
upd.resize(n << 2 | 3, false);
build(1, 0, n - 1, values);
}
void push(int i, int l, int r) {
if (upd[i]) {
applyUpd(lazy[i], ST[i], l, r);
if (l != r) {
pushUpd(lazy[i], lazy[i << 1], l, r, l, (l + r) / 2);
pushUpd(lazy[i], lazy[i << 1 | 1], l, r, (l + r) / 2 + 1, r);
upd[i << 1] = 1;
upd[i << 1 | 1] = 1;
}
upd[i] = false;
lazy[i] = T2();
}
}
void update(int i, int l, int r, int a, int b, T2 &u) {
if (l >= a and r <= b) {
pushUpd(u, lazy[i], a, b, l, r);
upd[i] = true;
}
push(i, l, r);
if (l > b or r < a)
return;
if (l >= a and r <= b)
return;
update(i << 1, l, (l + r) >> 1, a, b, u);
update(i << 1 | 1, (l + r) / 2 + 1, r, a, b, u);
ST[i] = merge(ST[i << 1], ST[i << 1 | 1]);
}
void update(int a, int b, T2 u) {
if (a > b) {
update(0, b, u);
update(a, n - 1, u);
return;
}
update(1, 0, n - 1, a, b, u);
}
T1 query(int i, int l, int r, int a, int b) {
push(i, l, r);
if (a <= l and r <= b)
return ST[i];
int mid = (l + r) >> 1;
if (mid < a)
return query(i << 1 | 1, mid + 1, r, a, b);
if (mid >= b)
return query(i << 1, l, mid, a, b);
return merge(query(i << 1, l, mid, a, b),
query(i << 1 | 1, mid + 1, r, a, b));
}
T1 query(int a, int b) {
if (a > b) {
return merge(query(a, n - 1), query(0, b));
}
return query(1, 0, n - 1, a, b);
}
void get_leaves(int i, int l, int r, vector<T1> &res) {
push(i, l, r);
if (l == r) {
res[l] = ST[i];
return;
}
get_leaves(i << 1, l, (l + r) / 2, res);
get_leaves(i << 1 | 1, (l + r) / 2 + 1, r, res);
}
void get_leaves(vector<T1> &res) {
res.resize(n);
get_leaves(1, 0, n - 1, res);
}
};
void pushUpd(int &u1, int &u2, int l1, int r1, int l2, int r2) { u2 += u1; }
void applyUpd(int &u, int &v, int l, int r) { v += u; }
int merge(int a, int b) { return 0; }
ll count_swaps(vector<int> shoes) {
ll swaps = 0;
int n = shoes.size();
vector<int> substract(n);
SegmentTreeLazy<int, int, merge, pushUpd, applyUpd> STL(substract);
map<int, set<int>> indexes;
// [isFirstNegative, [i, j]]
vector<pii> pairs;
for (int i = 0; i < n; i++) {
int shoe = shoes[i];
if (indexes[-shoe].empty()) {
indexes[shoe].insert(i);
continue;
}
int index = *(indexes[-shoe].begin());
indexes[-shoe].erase(index);
pairs.emplace_back(index, i);
}
sort(pairs.begin(), pairs.end());
for (auto &[left, right] : pairs) {
int normalizedLeft = left + STL.query(left, left);
int normalizedRight = right + STL.query(right, right);
bool isFirstNegative = shoes[left] < 0;
swaps += normalizedRight - normalizedLeft - isFirstNegative;
STL.update(left, right, 1);
}
return swaps;
}
