题目描述

给出一个长度为$n$的由小写字母组成的字符串$a$，设其中第$i$个字符为$a_i(1≤i≤n)$ 。

设删掉第$i$个字符之后得到的字符串为$s_i$，请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

输入格式

第一行一个整数$n$。

第二行一个长为$n$的由小写字母组成的字符串$a$。

输出格式

输出一行$n$个整数$k_1,k_2,……,k_n$，用空格隔开。表示$s_{k_1}<s_{k_2}<……<s_{k_n}$。

7
aabaaab

3 7 4 5 6 1 2

提示

对于所有数据，$1≤n≤10^6$。

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

对于另外20%的数据，$1≤n≤10^5$且任意两个相邻字符$a_i,a_{i+1}$不相等；

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

对于余下40%的数据，无特殊限制。