8574: Suffix Sort

链接：https://ac.nowcoder.com/acm/contest/33192/I
来源：牛客网

For a string $s$, if we record the first occurrence of each type of character in order as t1,t2,t3,…,tkt_1, t_2, t_3, \dots, t_kt1,t2,t3,…,tk, then the minimal representation of $s$ can be obtained by replacing all occurrence of t1t_1t1 in $s$ by the first character of the character set (a), replacing all occurrence of t2t_2t2 in $s$ by the second character of the character set (b), and so on.

For example, when the character set is lowercase, the minimal representation of “edcca” is “abccd”, and “xy” and “zt” are essentially the same in terms of minimal representation.

Your task is sorting all suffixes of $S$ with a special regularity.

For two suffixes S[i:]S[i:]S[i:] and S[j:]S[j:]S[j:], if the minimal representation of S[i:]S[i:]S[i:] is less than
the minimal representation of S[j:]S[j:]S[j:] in the lexicographic order, then S[i:]S[i:]S[i:] is less than S[j:]S[j:]S[j:] in the special regularity.

Please output the result array $sa[i]$ of the suffix sort with the special regularity. The $i$-th element of $sa[i]$ is the position of the first character in the i-th smallest suffix of $S$ with the special regularity.

The first line contains one integers $n$ ($1\le n\le 200000$).
The next line contains a string $S$ of length $n$. It is guaranteed that $S$ only consists of lowercase English alphabets.

Output $n$ integers in a single line, representing the answer.