#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2e5 + 10;
unordered_multiset<int> seg[4 * maxn];
int ind[4 * maxn];
vector<int> thing;
void build (int idx, int l, int r) {
if (l == r) {
ind[idx] = l;
seg[idx].insert(thing[l]);
return;
}
int m = (l + r) >> 1;
build(idx * 2, l, m);
build(idx * 2 + 1, m + 1, r);
for (auto v : seg[idx * 2]) {
seg[idx].insert(v);
}
for (auto v : seg[idx * 2 + 1]) {
seg[idx].insert(v);
}
}
void update (int idx, int l, int r, int i, int j) {
if (j < l || r < i) return;
if (i <= l && r <= j) {
ind[idx]++;
return;
}
int m = (l + r) >> 1;
update(idx * 2, l, m, i, j);
update(idx * 2 + 1, m + 1, r, i, j);
}
void remove_elm (int idx, int l, int r, int i) {
if (l == r) {
seg[idx].clear();
ind[idx] = -1e9;
return;
}
int m = (l + r) >> 1;
if (i <= m) {
remove_elm(idx * 2, l, m, i);
} else {
remove_elm(idx * 2 + 1, m + 1, r, i);
}
seg[idx].erase(seg[idx].find(thing[i]));
}
int query_idx (int idx, int l, int r, int i) {
if (l == r) return ind[idx];
int m = (l + r) >> 1;
if (i <= m)
return ind[idx] + query_idx(idx * 2, l, m, i);
else
return ind[idx] + query_idx(idx * 2 + 1, m + 1, r, i);
}
pair<int, int> query_find (int idx, int l, int r, int x) {
if (l == r) return {ind[idx], l};
int m = (l + r) >> 1;
if (seg[idx * 2].count(x) > 0) {
auto [index, real] = query_find(idx * 2, l, m, x);
return {ind[idx] + index, real};
}
else {
auto [index, real] = query_find(idx * 2 + 1, m + 1, r, x);
return {ind[idx] + index, real};
}
}
long long count_swaps(vector<int> s) {
thing.push_back(0);
int n = s.size();
deque<pair<int, int>> q;
for (int i = 1; i <= s.size(); i++) {
thing.push_back(s[i - 1]);
q.push_back({s[i - 1], i});
}
build(1, 1, n);
long long ans = 0;
while (!q.empty()) {
auto [v, i] = q.front();
q.pop_front();
int idx = query_idx(1, 1, n, i);
if (idx < 0) continue;
auto [nidx, nreal] = query_find(1, 1, n, -v);
remove_elm(1, 1, n, i);
remove_elm(1, 1, n, nreal);
update(1, 1, n, i, nreal);
int delta = nidx - idx - 1;
if (v > 0) delta++;
ans += delta;
}
return ans;
}
