P5334 [JSOI2019] Festival Celebration

JYY and the expedition team successfully completed their mission on Mars. Before leaving, the team happened to catch the Martians’ biggest annual festival, the “Balloon Festival”. However, the Martians face a yearly problem: how to arrange the balloons in the most visually pleasing way. JYY decides to ask you to design an algorithm to help the Martians solve this problem.

Before the celebration begins, the Martians prepare the balloons and string them onto a rope. The balloons, in order, can be seen as a string $S$ of length $n$ consisting of lowercase letters. Then, the Martians will add the balloons one by one, following the order of the string, onto a circular ring for the celebration, and perform a show to celebrate. The figure below shows the situation for the balloon string **cbbadbcd** at the $5$-th show. At this time, the balloons on the celebration ring are **cbbad**.  To make each show look better, the Martians want to adjust the order of the balloons on the ring before each show starts, so that the balloon arrangement for each show is the most visually pleasing. For a set of balloons (a string), the Martians define the most visually pleasing string as the **lexicographically smallest string** read along the rope direction on the celebration ring. For example, for **cbbad**, there are $5$ possible starting positions to read the string: - cbbad ($i=1$). - bbadc ($i=2$). - badcb ($i=3$). - adcbb ($i=4$). - dcbba ($i=5$). If there are multiple lexicographically smallest strings, the Martians want the one **closest to the rope head** (i.e. the smallest $i$). More rigorously, for a string $T$, define $$T_i=T[i……|T|]::T[1……i-1](1 \leq i \leq |T|)$$ where $::$ denotes string concatenation. Define $f(T)$ as the smallest $i$ ($1 \leq i \leq |T|$) such that $T_i=min(T_1,T_2,……,T_{|T|})$. JYY hopes you can help him design an algorithm so that the balloon arrangement for each show is the most visually pleasing. That is, for every prefix $S[1……i]$ ($1 \leq i \leq |S|$) of the given string $S$, compute $f(S[1……i])$.

There is only one line of input, containing a string $S$.

In one line, for each $i$ ($1 \leq i \leq |S|$), output an integer $f(S[1……i])$. Separate the numbers with spaces.

 Translated by ChatGPT 5