#include "shoes.h"
using namespace std;
typedef pair<int, int> pii;
const int maxn = 1e5 + 10;
multiset<int> seg[4 * maxn];
int ind[4 * maxn];
int lz[4 * maxn];
vector<int> thing;
void propagate (int idx, int l, int r) {
if (lz[idx] == 0) return;
int lazy = lz[idx];
lz[idx] = 0;
if (l == r) {
if (ind[idx] == -1) return;
ind[idx] += lazy;
return;
}
lz[idx * 2] += lazy;
lz[idx * 2 + 1] += lazy;
}
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) {
propagate(idx, l, r);
if (j < l || r < i) return;
if (i <= l && r <= j) {
lz[idx]++;
propagate(idx, l, r);
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) {
propagate(idx, l, r);
if (i < l || r < i) return;
if (l == r) {
seg[idx].erase(thing[i]);
ind[idx] = -1;
return;
}
int m = (l + r) >> 1;
remove_elm(idx * 2, l, m, i);
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) {
propagate(idx, l, r);
if (l == r) return ind[idx];
int m = (l + r) >> 1;
if (i <= m) return query_idx(idx * 2, l, m, i);
else return query_idx(idx * 2 + 1, m + 1, r, i);
}
pair<int, int> query_find (int idx, int l, int r, int x) {
propagate(idx, l, r);
if (l == r) return {ind[idx], l};
int m = (l + r) >> 1;
if (seg[idx * 2].count(x) > 0) return query_find(idx * 2, l, m, x);
else return query_find(idx * 2 + 1, m + 1, r, x);
}
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);
for (int i = 1; i <= n; i++) {
//cout << thing[i] << ' ';
}
//cout << '\n';
for (int i = 1; i <= n; i++) {
//cout << query_idx(1, 1, n, i) << ' ';
}
//cout << '\n';
int ans = 0;
while (!q.empty()) {
auto [v, i] = q.front();
q.pop_front();
int idx = query_idx(1, 1, n, i);
if (idx == -1) 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);
//cout << nidx << ' ' << idx << ' ' << nreal << '\n';
int delta = nidx - idx - 1;
if (v > 0) delta++;
//cout << delta << '\n';
ans += delta;
}
return ans;
}
