[SNOI2019] 字符串

题目描述

给出一个长度为$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}$。

输入输出样例

输入样例 #1

7
aabaaab

输出样例 #1

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%的数据,无特殊限制。