题目描述

给定一个由 $N$ 个 a 和 $N$ 个 b 组成的长度为 $2N$ 的字符串 $S$。

你可以从 $S$ 中选择一些字符。但对于每个 $i=1,2,\ldots,N$，你不能只选择 $S$ 中第 $i$ 个出现的 a 或第 $i$ 个出现的 b 中的一个。也就是说，对于每一对第 $i$ 个 a 和第 $i$ 个 b，要么都选，要么都不选。然后将选中的字符（按照 $S$ 中的顺序）拼接起来。

请你求出在满足上述条件的所有字符串中，字典序最大的一个。

输入格式

输入从标准输入中给出，格式如下：

$N$ $S$

输出格式

请输出满足条件的 $T$ 中，字典序最大的一个。

样例 1

输入

3
aababb

输出

abab

样例 2

输入

3
bbabaa

输出

bbabaa

样例 3

输入

6
bbbaabbabaaa

输出

bbbabaaa

样例 4

输入

9
abbbaababaababbaba

输出

bbaababababa

说明/提示

限制

• $1 \leq N \leq 3000$
• $S$ 是由 $N$ 个 a 和 $N$ 个 b 组成的长度为 $2N$ 的字符串。

样例解释 1

由 $S$ 的第 $1,3,4,6$ 个字符组成的子序列 $T$ 满足条件。

样例解释 2

也可以选择所有字符。

由 ChatGPT 4.1 翻译