#include "shoes.h"
#include <vector>
#include <cmath>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long ll;
// Fenwick Tree (Binary Indexed Tree) inversiyalarni sanash uchun
struct BIT {
int n;
vector<int> tree;
BIT(int n) : n(n), tree(n + 1, 0) {}
void update(int i, int delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
int query(int i) {
int sum = 0;
for (; i > 0; i -= i & -i) sum += tree[i];
return sum;
}
};
ll count_swaps(vector<int> s) {
int n = s.size();
int pairs = n / 2;
// Har bir o'lchamdagi poyabzal manzillarini saqlaymiz
vector<deque<int>> pos_left(n + 1), pos_right(n + 1);
for (int i = 0; i < n; i++) {
if (s[i] < 0) pos_left[abs(s[i])].push_back(i);
else pos_right[s[i]].push_back(i);
}
vector<int> target(n);
vector<bool> processed(n, false);
int current_target = 0;
for (int i = 0; i < n; i++) {
if (processed[i]) continue;
int size = abs(s[i]);
int l_idx, r_idx;
// Juftlikni topamiz
l_idx = pos_left[size].front(); pos_left[size].pop_front();
r_idx = pos_right[size].front(); pos_right[size].pop_front();
// Qoidaga ko'ra chap poyabzal (-size) birinchi turishi kerak
processed[l_idx] = processed[r_idx] = true;
target[l_idx] = current_target++;
target[r_idx] = current_target++;
}
// BIT yordamida inversiyalarni hisoblaymiz
BIT bit(n);
ll total_swaps = 0;
for (int i = 0; i < n; i++) {
// Element o'zidan o'ngda turgan, lekin aslida chapda bo'lishi kerak bo'lganlarni sanaydi
total_swaps += i - bit.query(target[i]);
bit.update(target[i] + 1, 1);
}
return total_swaps;
}
