解题思路

加密把 26 个小写字母分成若干个大小至少为 2 的环（置换），对原串 s 中每个字母换成其所在环的下一个字母得到 t。 因此对每个出现于 t 的字母 y，原串对应位置的字母一定是 y 在环中的前驱，记为 pre[y]；同时每个字母作为前驱最多用一次，记为 to[x] 表示 x 的后继。

目标：构造映射 pre / to，使得按 s[i] = pre[t[i]] 得到的 s 字典序最小，并且这组部分映射能扩展成“所有 26 个字母组成的、环长≥2 的置换”。

核心算法（贪心 + 末尾修正）

1. 依次扫描 t：

题目内容

对于一个由小写字母组成的字符串 $s$ ，我们可以按以下方式将其加密成字符串 $t$ ：

• 将所有 $26$ 个小写字母任意分成若干个大小至少为 $2$ 的环，每个字母恰好属于一个环;

• 对于原串中的每个字母，将其替换为所在环中的下一个字母。

这样可以得到加密后的字符串 $t$ 。

现在给定长度为 $n$ 的加密串 $t$ ，请你还原出可能的原字符串 $s$ 中字典序最小的一个，并输出该字符串。

【名词解释】字典序比较:从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的字母表顺序，字母序较小的字符串字典序也较小;如果比较到其中个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述

第一行输入一个整数 $n(1 ≦n≦2×10^5)$ ，表示加密串的长度。

第二行输入一个长度为 $n$ 、仅由小写字母组成的字符串 $t$ 。

输出描述

输出一个长度为 $n$ 的字符串 $s$ ，表示字典序最小的可能原字符串。保证总存在至少一个合法原串。

样例1

输入

4
azab

输出

babc

样例2

输入

6
ababca

输出

babadb