E - Synchronized Subsequence 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1600 点

問題文

N 個の a と N 個の b からなる，長さ 2N の文字列 S が与えられます。

あなたは S からいくつかの文字を選びます。ただし各 i = 1,2,...,N について，S で i 番目に出現する a と i 番目に出現する b から片方だけ選ぶことは出来ません。 そして選んだ文字たちを( S での順番通りに)結合します。

こうして得られる文字列のうち，辞書順で最大のものを求めて下さい。

制約

  • 1 \leq N \leq 3000
  • S は N 個の a と b からなる，長さ 2N の文字列である。

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

条件を満たす T のうち，辞書順で最大のものを出力して下さい。

入力例 1

3
aababb

出力例 1

abab

S の 1, 3, 4, 6 番目の文字からなる部分列 T は，条件を満たします。

入力例 2

3
bbabaa

出力例 2

bbabaa

全ての文字を選ぶことも可能です。

入力例 3

6
bbbaabbabaaa

出力例 3

bbbabaaa

入力例 4

9
abbbaababaababbaba

出力例 4

bbaababababa

Score : 1600 points

Problem Statement

You are given a string S of length 2N, containing N occurrences of a and N occurrences of b.

You will choose some of the characters in S. Here, for each i = 1,2,...,N, it is not allowed to choose exactly one of the following two: the i-th occurrence of a and the i-th occurrence of b. (That is, you can only choose both or neither.) Then, you will concatenate the chosen characters (without changing the order).

Find the lexicographically largest string that can be obtained in this way.

Constraints

  • 1 \leq N \leq 3000
  • S is a string of length 2N containing N occurrences of a and N occurrences of b.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the lexicographically largest string that satisfies the condition.

Sample Input 1

3
aababb

Sample Output 1

abab

A subsequence of T obtained from taking the first, third, fourth and sixth characters in S, satisfies the condition.

Sample Input 2

3
bbabaa

Sample Output 2

bbabaa

You can choose all the characters.

Sample Input 3

6
bbbaabbabaaa

Sample Output 3

bbbabaaa

Sample Input 4

9
abbbaababaababbaba

Sample Output 4

bbaababababa