题目内容

给定一个长度为 $n$ 的小写英文字母字符串 $s$，下标从 $1$ 开始。你可以执行至多一次如下定义的双对调操作：

选取三个整数 $i,j,k$，满足 $1 \le i \le j \le n$，$1 \le i-k$，$j+k \le n$ 且 $k>0$。然后同时交换 $s_i$ 与 $s_{i-k}$，并交换 $s_j$ 与 $s_{j+k}$。

在所有的可选操作中，找出能够使字符串字典序最小的结果，并输出该字符串。字典序比较定义为：从字符串的第一个字符开始逐个比较，直至出现不同位置，字符较小的一方字典序更小；若一个字符串是另一字符串的前缀，则较短的字符串字典序更小。

字符串的长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，仅由小写字母组成。

输入描述

第一行包含一个整数 $n$，表示字符串的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母构成。

输出描述

输出一个字符串，表示经过至多一次双对调操作后可以获得的字典序最小字符串。

样例1

输入

1
a

输出

a

说明

字符串长度为 1，无法找到满足 $k > 0$ 且 $1 \le i - k$ 的 $i, k$，因此不能执行任何操作，答案保持原字符串 a。

样例2

输入

3
cba

输出

bac

说明

原字符串为 cba。通过一次双对调操作，将位置 $1, 2, 3$ 上的字符分别替换为原 $s_2, s_3, s_1$（即循环左移一位），得到 bac。经比较，这是所有可行操作中字典序最小的结果。

样例3

输入

4
dabc

输出

abdc

说明

原字符串为 dabc。执行一次双对调，将 $s_1, s_2, s_3$ 分别变为原 $s_2, s_3, s_1$，而 $s_4$ 保持不变，得到 abdc。该字符串已是字典序最小的可能结果。