25653번 - Suffix Sort 다국어

문제

Grammy has a string $S$ of length $n$ that consists of lowercase English letters.

For a string $P,ドル reading it left to right, write down the letters that never occurred before as $t_1, t_2, t_3, \ldots, t_k$. For example, if $P =$"sesame", we write down 's', 'e', 'a', 'm'. The minimal representation $R(P)$ can be obtained by replacing every occurrence of $t_1$ in $P$ by the first character of the character set ("a"), replacing every occurrence of $t_2$ in $P$ by the second character of the character set ("b"), and so on.

For example, when the character set is lowercase English letters, the minimal representation of "sesame" is "abacdb", the minimal representation of "edcca" is "abccd", and minimal representations $R($"xy"$)$ and $R($"zt"$)$ are both "ab".

Your task is to sort all suffixes of $S$ by their minimal representation. Formally, denote suffix $S_i S_{i + 1} \ldots S_{n - 1} S_n$ as $S[i{:}]$. For two suffixes $S[i{:}]$ and $S[j{:}],ドル if $R(S[i{:}])$ is less than $R(S[j{:}])$ in lexicographical order, then $S[i{:}]$ has to occur before $S[j{:}]$ in the desired order.

Please output the result as an array of indices $\mathit{sa}$: the $i$-th element of $\mathit{sa}[i]$ must be the position of the first character in the $i$-th smallest suffix of $S$ in the desired order. Formally, the array must satisfy $$R(S[\mathit{sa}[1]{:}]) < R(S[\mathit{sa}[2]{:}]) < \ldots < R(S[\mathit{sa}[n]{:}])\text{.}$$

입력

The first line contains one integers $n$ (1ドル \le n \le 200,000円$).

The next line contains a string $S$ of length $n$. It is guaranteed that $S$ only consists of lowercase English alphabets.

출력

Output $n$ integers representing the answer.

제한

힌트