P3165 [CQOI2014] Sorting Robotic Arm

To sort items of varying heights in nondecreasing order, engineers invented a sorting robotic arm. It follows a simple rule: in the first operation, find the position $P_1$ of the lowest item and reverse the items from the first item from the left up to $P_1$ (i.e., reverse the subarray $[1, P_1]$); in the second operation, find the position $P_2$ of the second lowest item and reverse the items from the second item from the left up to $P_2$ (i.e., reverse the subarray $[2, P_2]$); and so on. Eventually, all items will be sorted.  The figure above shows an example with six items. Before the first operation, the lowest item is at position $4$, so the first through fourth items are reversed. Before the second operation, the second lowest item is at position $6$, so the second through sixth items are reversed. Your task is to write a program to determine the sequence of operations, namely, the position $P_i$ of the $i$-th lowest item before each operation, so the robotic arm can execute them. Note that if there are items with equal height, their relative order must remain the same after sorting.

The first line contains a positive integer $n$, the number of items to sort. The second line contains $n$ space-separated integers $P_i$, the height of each item.

Output one line containing $n$ space-separated integers $P_i$.

$N \le 100000$ $P_i \le 10^7$ Translated by ChatGPT 5