#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(a,i,n) for (int i=a;i<n;i++)
map<int, queue<int> > saan;
struct SegTree {
int l, r, val;
SegTree* lt, * rt;
void combine() {
val = lt->val + rt->val;
}
SegTree(int left, int right, vector<int>& a) {
l = left; r = right;
lt = rt = nullptr;
if (left==right) {
val = a[left];
return;
}
int mid = (l+r)>>1;
lt = new SegTree(l, mid, a);
rt = new SegTree(mid+1, r, a);
combine();
}
void update(int i){
if(l <= i && i <= r){
if (lt) {
lt->update(i);
rt->update(i);
combine();
}
else {
val++;
}
}
}
int query(int ql, int qr) {
if (qr < l || r < ql) { // completely out
return 0;
}
if ( ql <= l && r <= qr) { //completely in
return val;
}
return lt->query(ql, qr) + rt->query(ql, qr);
}
};
int count_swaps(vector<int> S) {
vector<int> arr;
int N=S.size(), ind=0, count=0;
for (int shoe : S) {
if (saan[shoe].empty()) {
saan[-shoe].push(ind + (shoe < 0)); //push the opposite
arr.push_back(ind + (shoe > 0));
ind += 2;
}
else {
arr.push_back(saan[shoe].front());
saan[shoe].pop();
}
}
vector<int> ex(100'000, 0);
SegTree* sgt = new SegTree(0, 99'999, ex);
for (int i=N-1; i>=0;i--) {
count += sgt->query(0, arr[i]-1);
sgt->update(arr[i]);
}
return count;
}
