解题思路

这题不能暴力枚举三元组 $(i,j,k)$，因为可行操作很多。 但它有很强的字典序性质，可以做到 $O(n\log n)$。

1. 把操作改写成位置形式

设左边交换的位置是 $(p,q)$，其中：

题目内容

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

具体地，给定一个长度为 $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

说明

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