#include "shoes.h"
#include <bits/stdc++.h>
struct SegmentTree {
int N;
std::vector<int> tree;
std::vector<int> lazy;
SegmentTree(int n) {
N = n;
tree.resize(4*N);
lazy.resize(4*N);
}
void push(int node, int left, int right) {
tree[node] += lazy[node] * (right - left + 1);
if (left != right) {
lazy[node*2] += lazy[node];
lazy[node*2+1] += lazy[node];
}
lazy[node] = 0;
}
int get(int node, int left, int right, int idx) {
push(node, left, right);
if (left > idx || right < idx) {
return 0;
}
if (left == idx && right == idx) {
return tree[node];
}
return get(node*2, left, (left+right)/2, idx) + get(node*2+1, (left+right)/2+1, right, idx);
}
void add(int node, int left, int right, int tl, int tr) {
push(node, left, right);
if (left > tr || right < tl) {
return;
}
if (left >= tl && right <= tr) {
lazy[node] += 1;
push(node, left, right);
return;
}
add(node*2, left, (left+right)/2, tl, tr);
add(node*2+1, (left+right)/2+1, right, tl, tr);
tree[node] = tree[node*2] + tree[node*2+1];
}
};
long long count_swaps(std::vector<int> s) {
int n = s.size();
std::map<int, std::vector<int>> idx;
for (int i = n-1;i >= 0; --i) {
idx[s[i]].push_back(i);
}
int64_t ans = 0;
SegmentTree st(n);
std::vector<bool> vis(n);
for (int i = 0;i < n; ++i) {
if (!vis[i]) {
int next = idx[-s[i]].back();
ans += next - i + st.get(1, 0, n-1, next) - st.get(1, 0, n-1, i) - (s[i] <= 0);
st.add(1, 0, n-1, i, next);
vis[next] = true;
idx[s[i]].pop_back();
idx[-s[i]].pop_back();
}
}
return ans;
}
