Suppose that for some \(A_i\), the number of \(j\) satisfying \(A_j < A_i\) is less than \(A_i\). Then, no matter how the elements are rearranged, the condition cannot be achieved. Conversely, if no such \(A_i\) exists, then a sequence satisfying the condition can always be constructed.

Remove all occurrences of the maximum value \(X\) of \(A\) from \(A\) temporarily, and solve the problem recursively. By the condition, even after removing \(X\), the sequence still has at least \(X\) elements remaining, so it suffices to insert all the removed copies of \(X\) right after the \(X\)-th element of the resulting sequence.

This induction also shows that the solution to this problem is in fact unique.

The issue is the time complexity. If the above procedure is implemented naively using an array, it takes \(O(N^2)\) time.

Solution 1: Balanced binary search tree

A “brute-force” approach (but without additional insight) is to use a balanced binary tree. The operation required by this procedure is insertion of an element at the \(k\)-th position, which can be done in \(O(\log N)\) time with a balanced binary tree. Thus, it takes \(O(N \log N)\) time in total.

However, it is rare for an AtCoder problem to require a balanced binary tree (which std::set cannot handle), and indeed there is another solution to this problem.

Solution 2: Stack

If we think of the construction method described above as fixing the elements of \(B\) one by one from the front, it is actually a greedy method that appends “the largest currently usable value” at each step. Thus, by managing the usable values with a stack, we obtain the following procedure.

Let \(C_x\) be the remaining count of the value \(x\). Prepare an empty sequence \(B\), and repeat the following steps until \(|B|=N\).

1. Let \(L\) be the current length of \(B\).
2. If \(C_L\gt 0\), append one \(L\) to the end of \(B\). Push the remaining copies of \(L\) onto the stack, set \(C_L=0\), and end this iteration.
3. Otherwise, if the stack is not empty, pop the value at the top of the stack and append it to the end of \(B\).
4. Otherwise, if the stack is empty, there is no sequence satisfying the condition.