#include "shoes.h"
#include <vector>
#include <map>
#include <deque>
using namespace std;
// Fenwick Tree (Binary Indexed Tree) for inversion counting
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int size) : n(size), bit(size + 2, 0) {}
void add(int index, int val) {
for (++index; index <= n + 1; index += index & -index)
bit[index] += val;
}
int sum(int index) {
int result = 0;
for (++index; index > 0; index -= index & -index)
result += bit[index];
return result;
}
};
// Main function required by the grader
long long count_swaps(vector<int> S) {
int n = S.size();
map<int, deque<int>> pos;
vector<bool> visited(n, false);
vector<int> target(n);
// Map positions of each shoe value
for (int i = 0; i < n; ++i)
pos[S[i]].push_back(i);
for (int i = 0; i < n; ++i) {
if (visited[i]) continue;
int shoe = S[i];
int pair_index;
if (shoe < 0) {
pair_index = pos[-shoe].front();
pos[-shoe].pop_front();
} else {
pair_index = pos[-shoe].front();
pos[-shoe].pop_front();
}
visited[i] = visited[pair_index] = true;
if (shoe < 0) {
target[i] = 0; // left shoe comes first
target[pair_index] = 1;
} else {
target[pair_index] = 0; // left shoe comes first
target[i] = 1;
}
}
// Count inversions on target to determine swaps needed
Fenwick tree(n);
long long swaps = 0;
for (int i = 0; i < n; ++i) {
swaps += i - tree.sum(target[i]);
tree.add(target[i], 1);
}
return swaps;
}
