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 可以将第一个括号移到末尾,从而将序列变成“()”,这是正确的括号序列。
在第二个示例中,无法最多移动一个括号以使顺序变得正确。
在第三个示例中,顺序已经正确,无需移动括号。