Prefix reversal

In the Laboratory of Intelligent Prefix Algorithms (LIPA), they are testing a Prefix-Reversing Machine (PRM). The machine works as follows: it receives as input a string $s$ of length $n$ and a sequence 1 \leq a_1 < a_2 < \ldots < a_k \leq n. Initially, the string $s$ is placed into a special internal register of the machine. Then, for each $i$ from $1$ to $k$, the machine takes the prefix [1..a_i] of the current string and reverses it. The string that remains in the register after the machine finishes is the result of the machine.

For example, if the input string is $\text{abacaba}$ and the sequence is a_1 = 2, a_2 = 4, the output will be the string $\text{caababa}$.

The scientists at LIPA want to find, for a given string, such a sequence so that the resulting string is as small as possible in lexicographical order. A string \alpha = \alpha_1\alpha_2 \ldots \alpha_n is lexicographically smaller than a string \beta = \beta_1\beta_2 \ldots \beta_m if, for some $k$, for all 1 \leq t \leq k it holds that \alpha_t = \beta_t, and either \alpha_{k+1} < \beta_{k+1}, or the length of $\alpha$ is $k$ and the length of $\beta$ is greater than $k$.

Help them determine the lexicographically smallest result that can be obtained.