#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN = 2e5 + 1;
int seg[4 * mxN];
int n;
void update(int tar, int l = 1, int r = n, int idx = 1) {
if (l == r) {
seg[idx] ^= 1;
return;
}
int mid = (l + r) >> 1;
if (tar <= mid) update(tar, l, mid, (idx << 1));
else update(tar, mid + 1, r, (idx << 1) + 1);
seg[idx] = seg[(idx << 1)] + seg[(idx << 1) + 1];
return;
}
int query(int tarl, int tarr, int l = 1, int r = n, int idx = 1) {
if (tarl > tarr) return 0;
if (tarl <= l && r <= tarr) return seg[idx];
else if (tarr < l || r < tarl) return 0;
int mid = (l + r) >> 1;
return query(tarl, min(tarr, mid), l, mid, (idx << 1)) + query(max(tarl, mid + 1), tarr, mid + 1, r, (idx << 1) + 1);
}
long long count_swaps(vector<int> s) {
n = s.size();
map<int, queue<int> > mp;
int cnt = 1;
int a[n + 1];
for (int i = 0; i < n; i++) {
if (!mp[s[i]].empty()) {
a[i] = mp[s[i]].front(); mp[s[i]].pop();
} else {
a[i] = cnt;
mp[-s[i]].push(cnt + 1);
cnt += 2;
}
}
for (int i = 0; i < n; i++) cerr << a[i] << ' ';
cerr << endl;
ll int ans = 0;
for (int i = 0; i < n; i++) {
ans += query(a[i] + 1, n);
update(a[i]);
}
return ans;
}
