← 返回题目列表

Codeforces · 1214/C

C. 错误序列

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

Petya 的朋友们给他做了一份生日礼物——一个括号序列。佩蒂亚对他的礼物非常失望,因为他梦想着正确的括号顺序,但他没有告诉他的朋友他的梦想,并决定自己修复礼物。

为了使一切正确,Petya 最多将一个括号从序列中的原始位置移动到任何其他位置。不允许颠倒括号(例如,将“(”变为“)”,反之亦然)。

我们提醒一下,如果满足以下条件,括号序列 $$$s$$$ 被称为正确的:

- $$$s$$$ 为空;
- $$$s$$$ 等于 "($$$t$$$)",其中 $$$t$$$ 是正确的括号序列;
- $$$s$$$ 等于 $$$t_1 t_2$$$,即 $$$t_1$$$ 和 $$$t_2$$$ 的串联,其中 $$$t_1$$$ 和 $$$t_2$$$ 是正确的括号序列。

例如,“(()())”、“()”是正确的,而“)(”和“())”则不正确。帮助 Petya 修复他的生日礼物,并了解他是否可以移动一个支架以使顺序正确。

输入

输入的第一行包含一个数字 $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — Petya 收到的生日序列的长度。

输入的第二行包含长度为 $$$n$$$ 的括号序列,包含符号“(”和“)”。

输出

如果 Petya 最多可以移动一个括号使他的顺序正确,则打印“Yes”。否则打印“否”。

示例

输入 #1

2
)(

输出 #1

Yes

输入 #2

3
(()

输出 #2

No

输入 #3

2
()

输出 #3

Yes

输入#4

10
)))))(((((

输出#4

No

注意

在第一个示例中,Petya 可以将第一个括号移到末尾,从而将序列变成“()”,这是正确的括号序列。

在第二个示例中,无法最多移动一个括号以使顺序变得正确。

在第三个示例中,顺序已经正确,无需移动括号。