#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
const int sz = 2e5 + 10;
int st[sz * 4];
int query(int ql, int qr, int le, int ri, int v) {
if (le > qr || ri < ql) return 0;
if (ql <= le && ri <= qr) return st[v];
int mi = le + (ri - le) / 2;
int ls = query(ql, qr, le, mi, v * 2);
int rs = query(ql, qr, mi + 1, ri, v * 2 + 1);
return ls + rs;
}
void update(int le, int ri, int k, int v) {
if (le == k && ri == k) {
st[v] = 1;
} else if (le <= k && k <= ri) {
int mi = le + (ri - le) / 2;
update(le, mi, k, v * 2);
update(mi + 1, ri, k, v * 2 + 1);
// cout << "UPD RANGE: " << le << ' ' << ri << '\n';
st[v] = st[v * 2] + st[v * 2 + 1];
}
}
long long count_swaps(std::vector<int> s) {
map<int,queue<int>>cl;
int n = s.size();
for (int i = 0; i < n; i ++) {
cl[s[i]].push(i);
}
long long r = 0;
for (int i = 0; i < n; i ++) {
auto it = query(i + 1, i + 1, 1, n, 1);
if (it != 0) continue;
int ix = cl[-s[i]].front();
int vs = i - query(1, i + 1, 1, n, 1);
int ve = ix - query(1, ix + 1, 1, n, 1);
// cout << vs << ' ' << ve << '\n';
r += (ve - vs);
if (s[i] < 0) {
r --;
}
cl[-s[i]].pop();
cl[s[i]].pop();
// cout << "IND " << i << ' ' << vs << '\n';
// update(i + 1, i + 1, 1, n, 1);
update(1, n, i + 1, 1);
// cout << "IND " << ix << ' ' << ve << '\n';
update(1, n, ix + 1, 1);
// update(ix + 1, ix + 1, 1, n, 1);
// cout << i << ' ' << ix << '\n';
// cout << "SUM OF ALL: " << query(1, n, 1, n, 1) << '\n';
}
return r;
}
