括号删除

题目描述

给定一个长度为 $N$ 的字符串 $S$,它由小写英文字母以及字符 ( 和 ) 组成。

请尽可能多次地执行以下操作,并输出操作后的字符串 $S$。

• 选择 $S$ 的一个连续子串,该子串以 ( 开头、以 ) 结尾,并且除首尾字符外不包含 ( 或 )。删除该子串。

可以证明,尽可能多次执行操作后得到的字符串 $S$ 是唯一确定的,与操作的执行方式无关。

输入格式

输入按以下格式从标准输入给出:

$N$
$S$

输出格式

输出答案。

样例

8
a(b(d))c

ac

下面是一种操作过程,操作后 $S$ 变为 ac。

删除由 $S$ 的第 4 到第 6 个字符组成的子串 (d),$S$ 变为 a(b)c。

删除由第 2 到第 4 个字符组成的子串 (b),$S$ 变为 ac。

此后无法再执行操作。

5
a(b)(

a(

2
()

操作后的字符串 $S$ 可能为空。

6
)))(((

)))(((

数据范围

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