#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int N = 2e5 + 5;
int T[4 * N], a[N], n, m;
void build(int s = 0, int e = n, int v = 1){
if (e - s == 1){
T[v] = a[s];
return;
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
build(s, mid, lc);
build(mid, e, rc);
T[v] = T[lc] + T[rc];
}
int query(int l, int r, int s = 0, int e = n, int v = 1){
if (l <= s && e <= r){
return T[v];
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
if (r > mid){
int ans = query(l, r, mid, e, rc);
if (l < mid) ans += query(l , r, s, mid, lc);
return ans;
}
else return query(l , r, s, mid, lc);
}
void update(int val, int idx, int s = 0, int e = n, int v = 1){
if (idx < s or idx >= e) return;
if (e - s == 1){
T[v] = val;
return;
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
update(val, idx, s, mid, lc);
update(val, idx, mid, e, rc);
T[v] = T[lc] + T[rc];
}
long long count_swaps(vector<int> s) {
n = s.size();
for (int i = 0; i < n; i++) a[i] = 1;
build();
map<int, deque<int>> C;
for (int i = 0; i < n; i++){
s[i] *= -1;
C[-s[i]].push_back(i);
}
int vis[n] = {};
long long ans = 0;
for (int i = 0; i < n; i++){
if (vis[i]) continue;
int idx = C[s[i]].front();
vis[i] = vis[idx] = 1;
C[s[i]].pop_front();
C[-s[i]].pop_front();
update(0, i);
update(0, idx);
// cout << i << ' ' << idx << endl;
int v = query(i, idx);
// int v = 1;
ans += v + (s[i] < 0);
}
return ans;
}
// int main(){
// cout << count_swaps({2, 1, -1, -2});
// }
