103073: [Atcoder]ABC307 D - Mismatched Parentheses

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

)))(((

问题描述

给你一个长度为 N 的字符串 S，由小写英文字母和字符 ( 和 ) 组成。

• 尽可能多的执行以下操作： 选择并删除一个 S 的连续子串，该子串以 ( 开头，以 ) 结尾，并且除了第一个和最后一个字符外不包含其他 ( 或 )。

可以证明，执行尽可能多的操作后的字符串 S 是唯一确定的，不会依赖于执行方式。

约束

• $1 \leq N \leq 2 \times 10^5$
• N 是一个整数。
• S 是一个长度为 N 的字符串，由小写英文字母和字符 ( 和 ) 组成。

输入

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

$N$
$S$

输出

打印答案。

样例输入 1

8
a(b(d))c

样例输出 1

ac

以下是一种可能的过程，使 S 变为 ac：

• 删除由 S 的第四个到第六个字符形成的子串 (d)，使其变为 a(b)c。
• 删除由 S 的第二个到第四个字符形成的子串 (b)，使其变为 ac。
• 无法再执行操作。

样例输入 2

5
a(b)(

样例输出 2

a(

样例输入 3

2
()

样例输出 3

执行过程后的字符串 S 可能为空。

样例输入 4

6
)))(((