P4402 [CERC2007] Robotic Sort

SORT is a company that provides sorting services with the motto: "Order is the most beautiful." Their job is to arrange certain items in order through a sequence of moves. The work rule allows only the following method to sort:  First find the position of the smallest-labeled item, denoted $P_1$, then reverse the segment $[1, P_1]$. Next find the position of the second smallest item, denoted $P_2$, and reverse the segment $[2, P_2]$... and so on. The figure shows an example with $6$ items. The smallest item is at position $4$. Therefore, we first reverse the first $4$ items. The second smallest item is at the last position, so the next operation is to reverse items $2 \sim 6$. The third step is to reverse items $3 \sim 4$... There may be duplicate labels in the input. If multiple items have the same label, operate on them according to their original input order.

The input has two lines. The first line contains an integer $N (1 \leq N \leq 10^5)$, the number of items. The second line contains $N$ space-separated integers, the initial labels $A_i (0 \leq A_i \leq 10^7)$ of the $N$ items.

Output a single line with $N$ space-separated positive integers $P_1, P_2, P_3 \cdots, P_N$, where $P_i$ is the position of the $i$-th smallest item before the $i$-th operation. Note: If before the $i$-th operation the $i$-th smallest item is already at the correct position $P_i$, we reverse the segment $[P_i, P_i]$ (a single item).

Translated by ChatGPT 5