题目背景

本来是 R11 签到，但是比赛锅了，所以变成题库里的普通题了。大家一起骂比赛负责人 @。

题目描述

小 $\text A$ 最近学习了两个新的排序算法：序列排序和字符串后缀排序，只不过，他的后缀排序，有些不正宗。

void suffix_sort(string &s){
    std::sort(s.begin(),s.end());
}

这一天你突然看到了小 $\text A$ 的“后缀排序”算法，并对其表示不屑。

“你这啥啊？”你嘲笑道。

“你是不是不会后缀排序？还来嘲笑我？有本事，你给这个字符串后缀排序！”

“来就来！”

当然，小 $\text A$ 为了刁难你，把字符串的长度设置成 $10^6$，但你仍然爽快迎战，拿到了这个字符串，却不由得笑出了声。它甚至已经经过了小 $\text A$ 的“后缀排序”！

输入格式

第一行输入一个正整数 $n$，表示字符串的长度。

第二行输入一个长度为 $n$ 的字符串。保证这个字符串是“后缀排序”得到的，且仅包含小写字母。

输出格式

输出一行 $n$ 个在 $[1,n]$ 间的整数，必须互不相同，表示第 $i$ 个后缀在所有后缀中的排名（即 rk[i]）。

7
aaabbbc

1 2 3 4 5 6 7

3
aaa

3 2 1

提示

样例解释 1

所有后缀排名如下：aaabbbc<aabbbc<abbbc<bbbc<bbc<bc<c。

样例解释 2

所有后缀排名如下：a<aa<aaa。

数据范围

$1\le n\le 10^6$。保证字符串仅由小写字母组成，且经过了小 $\text A$ 在题面中给出的代码“后缀排序”。

• Subtask 1：$n\le 100$，$50$ 分。$2$ 秒。
• Subtask 2：$n\le 10^5$，$10$ 分。$2$ 秒。
• Subtask 3：$n\le 10^6$，$40$ 分。$2$ 秒。

保证时限足够大，用不优化的 cout 都能过。

如果你实在看不懂什么叫“经过了小 $\text A$ 的后缀排序”，你可以认为数据如下生成：

string generate_input(){
    string s=generate_initial_string();//生成原本的字符串
    suffix_sort(s);//该函数即题面中的后缀排序
    return s;
}