#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using LL = long long;
#define all(V) V.begin(), V.end()
template <typename DT> using ordered_set = tree <DT, null_type, less <DT>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename DT> using minheap = priority_queue < DT, vector <DT>, greater <DT> >;
template <class T> bool chMax (T &x, T y) { return y > x ? x = y, 1 : 0; }
template <class T> bool chMin (T &x, T y) { return y < x ? x = y, 1 : 0; }
#include "shoes.h"
template <typename DT> class BIT {
public:
vector <DT> tree;
int n;
BIT (int n) {
this->n = n;
tree.assign (n, 0);
}
BIT (const vector <DT> &a) : BIT (a.size()) {
for (int i = 0; i < n; i++) add (i, a[i]);
}
DT sum (int r) {
DT ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1) ret += tree[r];
return ret;
}
DT sum (int l, int r) {
if (l > r) return 0;
return sum(r) - sum(l - 1);
}
void add (int idx, DT delta) {
for (; idx < n; idx = idx | (idx + 1)) tree[idx] += delta;
}
};
// BIT<LL> pref(mxN);
LL count_swaps (vector <int> S) {
int n = S.size ();
vector < queue <int> > left (n + 1), right (n + 1);
for (int i = 0; i < n; i++) {
if (S[i] < 0) left[-S[i]].push (i);
else right[S[i]].push (i);
}
BIT<int> Tree (n);
vector <int> visited (n);
LL ans = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
int need = -S[i];
if (need < 0) {
int pos = left[-need].front ();
left[-need].pop ();
ans += pos - i - 1 - Tree.sum (i + 1, n - 1) + Tree.sum (pos + 1, n - 1) + 1;
Tree.add (pos, +1);
visited[pos] = 1;
right[S[i]].pop ();
} else {
int pos = right[need].front ();
right[need].pop ();
ans += pos - i - 1 - Tree.sum (i + 1, n - 1) + Tree.sum (pos + 1, n - 1);
Tree.add (pos, +1);
visited[pos] = 1;
left[-S[i]].pop ();
}
}
return ans;
}
// int main() {
// cin.tie (nullptr) -> ios_base :: sync_with_stdio (false);
// cout << count_swaps({-2, 2, 2, -2, -2, 2}) << '\n';
// return 0;
// }
