解题思路

给定只含小写字母的字符串 s（长度为 n），定义“中位符”为：将字符按字典序（从小到大）排序后，取第 ceil(n/2) 个字符（从 1 开始计数）。

直接排序可做，但更高效的方法是利用字母表只有 26 个字符这一事实，使用计数排序（桶计数）：

1. 统计 26 个小写字母在字符串中的出现次数 cnt[0..25]。
2. 计算目标排名 k = (n + 1) // 2（即 ceil(n/2)）。
3. 从 a 到 z 依次累加出现次数，第一次使前缀和 >= k 的字母即为答案。

题目内容

给定一个长度为 $n$ 仅由小写字组成的字符串 "$s$"，请输出它的中位符。

定义一个字符串的”中位符”为将该字符串按字典序(从小到大)排序后第 $[\frac {n}{2}]$个字符(字符从 $1$ 开始计数);

字符的字典序即其对应的 $ASCII$ 码 ($a<···<z$)。

在这里，$[x]$ 代表对 $z$ 进行上取整操作。

输入描述

输入包含两行:

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

第二行输入长度为 $n$ 的字符串 "$s$"，仅由小写字母组成。

输出描述

输出一个字符，表示字符串"$s$"的中位符。

样例1

输入

3
cba

输出

b