P5329 [SNOI2019] 字符串

给出一个长度为$n$的由小写字母组成的字符串$a$，设其中第$i$个字符为$a_i(1≤i≤n)$ 。 设删掉第$i$个字符之后得到的字符串为$s_i$，请按照字典序对$s_1,s_2,……,s_n$从小到大排序。若两个字符串相等，则认为编号小的字符串字典序更小。

无

无

对于所有数据，$1≤n≤10^6$。 对于10%的数据，$1≤n≤2000$； 对于另外20%的数据，$1≤n≤10^5$且任意两个相邻字符$a_i,a_{i+1}$不相等； 对于另外30%的数据，$1≤n≤10^5$； 对于余下40%的数据，无特殊限制。