#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long arr[200005], seg[4*200005];
void build(long long n, long long l, long long r) {
if (l == r) {
seg[n] = arr[l];
} else {
long long m = (l+r)/2;
build(2*n, l, m);
build(2*n+1, m+1, r);
seg[n] = seg[2*n] + seg[2*n+1];
}
}
void update(long long n, long long l, long long r, long long i, long long v) {
if (l == r) {
seg[n] = v;
} else {
long long m = (l+r)/2;
if (l <= i && i <= m) {
update(2*n, l, m, i, v);
} else {
update(2*n+1, m+1, r, i, v);
}
seg[n] = seg[2*n] + seg[2*n+1];
}
}
long long query(long long n, long long l, long long r, long long a, long long b) {
if (b < l || r < a) {
return 0;
} else if (a <= l && r <= b) {
return seg[n];
} else {
long long m = (l+r)/2;
return query(2*n, l, m, a, b) + query(2*n+1, m+1, r, a, b);
}
}
long long count_swaps(vector<int> s) {
long long n = s.size(), ans = 0;
vector<long long> vis(n, 0);
map<long long, vector<long long>> num;
for (long long i = 0; i < n; i++) {
num[s[i]].push_back(i);
arr[i] = 1;
}
for (auto c : num) {
reverse(num[c.first].begin(), num[c.first].end());
}
build(1, 0, n-1);
for (long long i = 0; i < n; i++) {
if (vis[i]) {
continue;
}
long long co = 0, ind = -1;
long long j = s[i]*-1;
ind = num[j].back();
num[s[i]].pop_back();
num[j].pop_back();
co = query(1, 0, n-1, i, ind)-2;
vis[i] = 1;
vis[ind] = 1;
update(1, 0, n-1, i, 0);
update(1, 0, n-1, ind, 0);
ans += co;
if (j < 0) {
ans++;
}
}
return ans;
}
