D - Mismatched Parentheses 解説 /

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

配点 : 400

問題文

英小文字および (, ) からなる長さ N の文字列 S が与えられます。
以下の操作を可能な限り繰り返したあとの S を出力してください。

  • S の連続部分文字列であって、最初の文字が ( かつ 最後の文字が ) かつ 最初と最後以外に () も含まないものを自由に 1 つ選び削除する

なお、操作を可能な限り繰り返したあとの S は操作の手順によらず一意に定まることが証明できます。

制約

  • 1 \leq N \leq 2 \times 10^5
  • N は整数である
  • S は英小文字および (, ) からなる長さ N の文字列である

入力

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

N
S

出力

答えを出力せよ。


入力例 1

8
a(b(d))c

出力例 1

ac

例えば、以下の手順により操作後の Sac となります。

  • S4 文字目から 6 文字目までからなる部分文字列 (d) を削除する。Sa(b)c となる。
  • S2 文字目から 4 文字目までからなる部分文字列 (b) を削除する。Sac となる。
  • これ以上操作を行うことはできない。

入力例 2

5
a(b)(

出力例 2

a(

入力例 3

2
()

出力例 3


操作後の S は空文字列になる可能性があります。


入力例 4

6
)))(((

出力例 4

)))(((

Score : 400 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters and the characters ( and ).
Print the string S after performing the following operation as many times as possible.

  • Choose and delete a contiguous substring of S that starts with (, ends with ), and does not contain ( or ) other than the first and last characters.

It can be proved that the string S after performing the operation as many times as possible is uniquely determined without depending on how it is performed.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • N is an integer.
  • S is a string of length N consisting of lowercase English letters and the characters ( and ).

Input

The input is given from Standard Input in the following format:

N
S

Output

Print the answer.


Sample Input 1

8
a(b(d))c

Sample Output 1

ac

Here is one possible procedure, after which S will be ac.

  • Delete the substring (d) formed by the fourth to sixth characters of S, making it a(b)c.
  • Delete the substring (b) formed by the second to fourth characters of S, making it ac.
  • The operation can no longer be performed.

Sample Input 2

5
a(b)(

Sample Output 2

a(

Sample Input 3

2
()

Sample Output 3


The string S after the procedure may be empty.


Sample Input 4

6
)))(((

Sample Output 4

)))(((