Description

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.

Input Format

The first line contains an integer $n$.

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

Output Format

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

7
aabaaab

3 7 4 5 6 1 2

Hint

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