#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)
map<ll, queue<ll> > saan;
struct SegTree {
ll l, r, val;
SegTree* lt, * rt;
void combine() {
val = lt->val + rt->val;
}
SegTree(ll left, ll right, vector<ll>& a) {
l = left; r = right;
lt = rt = nullptr;
if (left==right) {
val = a[left];
return;
}
ll mid = (l+r)>>1;
lt = new SegTree(l, mid, a);
rt = new SegTree(mid+1, r, a);
combine();
}
void update(ll i){
if(l <= i && i <= r){
if (lt) {
lt->update(i);
rt->update(i);
combine();
}
else {
val++;
}
}
}
ll query(ll ql, ll 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);
}
};
ll count_swaps(vector<int> S) {
vector<ll> arr;
ll N=S.size(), ind=0, count=0;
for (auto 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<ll> ex(300'005, 0);
SegTree* sgt = new SegTree(0, 300'004, ex);
for (ll i=N-1; i>=0;i--) {
count += sgt->query(0, arr[i]-1);
sgt->update(arr[i]);
}
return count;
}
