思路

• 关键观察：

  • 操作会改动四个位置，最靠左的改动是 $p=i-k$。若能让 $s_q$（其中 $q=i$）移动到 $p$ 且 $s_q<s_p$，则新串在位置 $p$ 就已更优，之后怎么改都不会更差。
  • 为使第二次交换尽量不影响前缀字典序，令 $j=n-k$（把第二次交换推到最右，交换 $(n-k,n)$）。

• 两种获益方式：

  1. 把更小的字符左移到更早位置：对每个 $p$，可选 $q\in[p+1,\ \lfloor\frac{n+p-1}{2}\rfloor]$ 且 $k=q-p$。若区间内存在 $s_q<s_p$，取最早的 $p$ 与使 $s_q$ 最小的 $q$，再取 $j=n-k$ 执行，答案最优。

题目内容

为了提升小红书笔记标签的可读性，我们计划对标签字符串进行一次双向字符置换操作，以获得更小的字典序结果。

具体地，给定一个长度为 $n$ 的字符串 $s$ (下标从 $1$ 开始)，你可以进行多一次如下作：

• 选取三个整数 $(i,j,k)$ ，满足 $1≤i≤j≤n，1≤i-k，j+k≤n$ 且 $k>0$ ;

• 将 $s_i$ 与 $s_{i-k}$ 交换，并将 $s_j$ 与 $s_{j+k}$ 交换。

请你在所有可行操作中，找出能够使字符串字典序最小的结果，并输出该字符串。

【名词解释】

字典序比较：从字符串第一个字符开始逐个比较，直至出现不同位置，字符较小的一方字典序更小；若一个字符串是另一前缀，则较短字符串字典序更小。

输入描述

第一行输入一个正整数 $n(1≤n≤2×10^5)$ ，表示字符串长度。

第二行输入一个由小写字母构成的字符串 $s$ .

输出描述

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

样例1

输入

5
baced

输出

abcde

说明

样例解释1

在这个样例中，选择三元组 $(2,4,1)$ 可得到结果 “$abcde$" 。