#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
typedef long long ll;
struct SegTree {
int n;
vector<int> tree;
SegTree(int n) : n(n), tree(4*n, 0) {}
void build(int node, int l, int r) {
if (l == r) {
tree[node] = 1;
return;
}
int mid = (l + r) / 2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
tree[node] = tree[2*node] + tree[2*node+1];
}
void update(int node, int l, int r, int pos) {
if (l == r) {
tree[node] = 0;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos);
else update(2*node+1, mid+1, r, pos);
tree[node] = tree[2*node] + tree[2*node+1];
}
int query(int node, int l, int r, int ql, int qr) {
if (qr < l || r < ql) return 0;
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
return query(2*node, l, mid, ql, qr) +
query(2*node+1, mid+1, r, ql, qr);
}
};
ll solve8(vector<int> &s)
{
int n = s.size();
// positions of each value
unordered_map<int, deque<int>> pos;
for (int i = 0; i < n; i++)
pos[s[i]].push_back(i);
SegTree st(n);
st.build(1, 0, n-1);
vector<bool> removed(n, false);
ll ans = 0;
for (int i = 0; i < n; i++)
{
if (removed[i]) continue;
int x = s[i];
pos[x].pop_front();
// find first alive occurrence of -x
while (!pos[-x].empty() && removed[pos[-x].front()])
pos[-x].pop_front();
int j = pos[-x].front();
pos[-x].pop_front();
// number of active elements strictly between i and j
int swaps = st.query(1, 0, n-1, i+1, j-1);
ans += swaps;
// same correction as your code
if (x > 0)
ans++;
// remove both
st.update(1, 0, n-1, i);
st.update(1, 0, n-1, j);
removed[i] = removed[j] = true;
}
return ans;
}
long long count_swaps(std::vector<int> S)
{
return solve8(S);
}
