题目描述

给定一个长度为 $N$ 的字符串 $s$。第 $i$ 个字符记作 $s_i$。

すぬけ君会按照以下步骤对 $s$ 进行变换：

• 选择 $(1,2,\ldots,N)$ 的一个长度为偶数的（不一定连续）子序列 $x=(x_1, x_2, \ldots, x_{2k})$（$k=0$ 也可以）。
• 将 $s_{x_1}$ 与 $s_{x_{2k}}$ 交换。
• 将 $s_{x_2}$ 与 $s_{x_{2k-1}}$ 交换。
• 将 $s_{x_3}$ 与 $s_{x_{2k-2}}$ 交换。
• $\vdots$
• 将 $s_{x_k}$ 与 $s_{x_{k+1}}$ 交换。

请你求出，经过すぬけ君操作后，$s$ 可能变成的所有字符串中，字典序最小的字符串。

什么是字典序？字典序简单来说就是“单词在字典中的排列顺序”。更严格地说，判断两个不同字符串 $S$ 和 $T$ 的大小的方法如下：

记“$S$ 的第 $i$ 个字符”为 $S_i$。若 $S$ 字典序小于 $T$，记作 $S < T$；若大于，记作 $S > T$。

1. 取 $S$ 和 $T$ 中较短的长度为 $L$。依次比较 $i=1,2,\dots,L$ 的 $S_i$ 和 $T_i$ 是否相同。
2. 若存在 $S_i \neq T_i$，取最小的此类 $i$ 为 $j$，比较 $S_j$ 和 $T_j$。若 $S_j$ 的字母序小于 $T_j$，则 $S < T$，否则 $S > T$，算法结束。
3. 若所有 $S_i = T_i$，则比较长度，若 $S$ 比 $T$ 短，则 $S < T$，否则 $S > T$，算法结束。

输入格式

输入从标准输入读入，格式如下：

$N$ $s$

输出格式

请输出すぬけ君操作后可能得到的所有字符串中字典序最小的一个。

样例 1

输入

4
dcab

输出

acdb

样例 2

输入

2
ab

输出

ab

样例 3

输入

16
cabaaabbbabcbaba

输出

aaaaaaabbbbcbbbc

样例 4

输入

17
snwfpfwipeusiwkzo

输出

effwpnwipsusiwkzo

说明/提示

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $s$ 是仅由小写英文字母组成的长度为 $N$ 的字符串

样例解释 1

• 当 $x=(1,3)$ 时，仅 $s_1$ 和 $s_3$ 被交换。操作后 $s$ 变为 acdb，是字典序最小的。

样例解释 2

• 当 $x=()$ 时，操作后 $s$ 仍为 ab，是字典序最小的。注意 $x$ 的长度为 $0$ 也是允许的。

由 ChatGPT 4.1 翻译