Subtask 1

It suffices to count inversions by iterating over all pairs of indices (including ~j < i~).

Time Complexity: ~\mathcal{O}(N^2)~

Query Count: ~N(N-1)~

Subtask 2

Optimize the subtask ~1~ solution by iterating over all pairs of indices excluding ~j \le i~.

Time Complexity: ~\mathcal{O}(N^2)~

Query Count: ~\frac{N(N-1)}{2}~

Subtask 3

This subtask was intended to reward solutions that use a heuristic that has a bad query constant.

Subtask 4

First, query ~Q_2~ heights. If there are more ~Q_2~ queries than people, output the permutation.

For the heights that were not found in the ~Q_2~ queries, insert them into an array and sort it with any built-in function but create a custom comparator to interact with the grader.

After sorting it, output the permutation.

Time Complexity: ~\mathcal{O}(N \log N)~

Query Count: ~\min(N, Q_2) + \max(0, (N-Q_2) \log(N-Q_2))~

Note that other solutions that use probabilistic lemmas also suffice since the grader is not adaptive.