附加文件

题目描述

给出一个字符串 $S$，长度为 $n$。

设删掉 $S$ 的第 $k$ 个字符得到的字符串为 $T_k$（$1 ≤ k ≤ n$）。

你的任务是，将 $T_1, T_2, ……, T_n$ 按字典序从小到大排序。若 $T_i == T_j$，则认为 $T_{min(i,j)}$ 字典序更小。

输入格式

第一行：一个整数 $n$；

第二行：一个字符串 $S$，长度为 $n$，全部为小写英文字母。

输出格式

一行，包含 n 个整数 $i_1,i_2,……,i_n$，表示 $T_{i_1} < T_{i_2} < …… < T_{i_n}$。数与数之间以一个空格隔开。

样例输入

7
aabaaab

样例输出

3 7 4 5 6 1 2

数据范围

$10$% 的数据，$1 ≤ n ≤ 2000$；

另外 $20$% 的数据，$1 ≤ n ≤ 10^5$ 且 $S$ 中任意两个相邻字符不同；

另外 $30$% 的数据，$1 ≤ n ≤ 10^5$；

剩余 $40$% 的数据，$1 ≤ n ≤ 10^6$。