#A1051. 封印之书·最小字典序之卷

封印之书·最小字典序之卷

Description

漩涡鸣人正在忍者学校的图书馆里偷偷翻阅封印之书,突然发现了一串神秘的忍术咒文(由小写字母组成)。他需要将这串咒文的所有字符依次封印(压入栈),并在解封(弹出栈)时,按照某种顺序重新排列。

然而,由于鸣人查克拉控制不够精细,解封的顺序会影响最终咒文的效果。为了确保不会引发意外,他必须找到所有可能的解封序列中字典序最小的那个,否则可能会召唤出不受控制的通灵兽!

任务描述:

给定一个长度为 nn 的、仅由小写字母组成的字符串(代表忍术咒文),按顺序依次将其字符压入栈中。在所有可能的出栈序列中,找出字典序最小的那个,并输出它。

Format

Input

输入第一行, 一个正整数nn

输入第二行,一个长度为nn的字符串

Output

输出字典序最小的满足要求的答案

Samples

样例输入

样例输入

3
fad

样例输出

adf

样例解释

字符f、a、d依次进栈,所有出栈的可能性有: {fad}、{fda}、{afd}、{adf}、{daf} 其中 {adf} 的字典序最小

Limitation

对于30%30\% 的数据,1n101 \leq n \leq 10

对于60%60\% 的数据,1n1031 \leq n \leq 10^3

对于100%100\%的数据,1n1051 \leq n \leq 10^5