← 返回题目列表

AtCoder · abc307_d

G. 括号不匹配

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

给你一个字符串 S 长度 N 由小写英文字母和字符组成 ( 和 ).
打印字符串 S 尽可能多次执行以下操作后。

  • 选择并删除 的连续子字符串 S 开头为 (,以 ),并且不包含 ( or ) 除了第一个和最后一个字符之外。

可以证明字符串 执行尽可能多次操作后的 S 被唯一地确定,而不依赖于它是如何执行的。

约束

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

输入

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

N
S

输出

打印答案。


示例输入 1

8
a(b(d))c

示例输出 1

ac

这是一种可能的程序,之后 S 将是 ac.

  • 删除子字符串 (d) 由第四到第六个字符组成 S,使其 a(b)c.
  • 删除子字符串 (b) 由第二到第四个字符组成 S,使其 ac.
  • 无法再执行该操作。

示例输入 2

5
a(b)(

示例输出 2

a(

示例输入 3

2
()

示例输出 3


字符串 S 程序后可能为空。


示例输入 4

6
)))(((

示例输出 4

)))(((