P5329 [SNOI2019] String

Given a string $a$ of length $n$ consisting of lowercase letters, let its $i$-th character be $a_i(1\le i\le n)$. Let $s_i$ be the string obtained after deleting the $i$-th character. Sort $s_1,s_2,\cdots,s_n$ in increasing lexicographical order. If two strings are equal, then the one with the smaller index is considered lexicographically smaller.

The first line contains an integer $n$. The second line contains a string $a$ of length $n$ consisting of lowercase letters.

Output one line with $n$ integers $k_1,k_2,\cdots,k_n$, separated by spaces, meaning that $s_{k_1}

Constraints: For all testdata, $1\le n\le 10^6$. For $10\%$ of the testdata, $1\le n\le 2000$. For another $20\%$ of the testdata, $1\le n\le 10^5$ and any two adjacent characters $a_i,a_{i+1}$ are not equal. For another $30\%$ of the testdata, $1\le n\le 10^5$. For the remaining $40\%$ of the testdata, there are no special constraints. Translated by ChatGPT 5