Bad Sequence

题意翻译

## 题目描述 给出一个长度为 $n$ 的括号序列 $s$ , 求出 $s$ 能否通过移动不超过 $1$ 个括号的位置, 使得这个括号序列变成一个正确的括号序列. 我们定义满足下面任意一个条件的括号序列 $S$ 为一个正确的括号序列: - $S$ 是一个空串 - $S = (t)$ , 其中 $t$ 是一个正确的括号序列 - $S = t_1 + t_2$ , 其中 $t_1$ , $t_2$ 都是正确的括号序列, '$+$' 运算定义为字符串的拼接. ## 输入格式 第一行一个正整数 $n$ 表示给出的括号序列的长度. 第二行一个仅包含 $($ 和 $)$ 的长度为 $n$ 的字符串, 表示给出的括号序列 $s$ . ## 输出格式 一行一个字符串, 如果给出的括号序列满足题目的条件, 则输出 "Yes" , 否则输出 "No" (不含引号). ## 数据范围 $1 \leq n \leq 200000$

题目描述

Petya's friends made him a birthday present — a bracket sequence. Petya was quite disappointed with his gift, because he dreamed of correct bracket sequence, yet he told his friends nothing about his dreams and decided to fix present himself. To make everything right, Petya is going to move at most one bracket from its original place in the sequence to any other position. Reversing the bracket (e.g. turning "(" into ")" or vice versa) isn't allowed. We remind that bracket sequence $ s $ is called correct if: - $ s $ is empty; - $ s $ is equal to "( $ t $ )", where $ t $ is correct bracket sequence; - $ s $ is equal to $ t_1 t_2 $ , i.e. concatenation of $ t_1 $ and $ t_2 $ , where $ t_1 $ and $ t_2 $ are correct bracket sequences. For example, "(()())", "()" are correct, while ")(" and "())" are not. Help Petya to fix his birthday present and understand whether he can move one bracket so that the sequence becomes correct.

输入输出格式

输入格式

First of line of input contains a single number $ n $ ( $ 1 \leq n \leq 200\,000 $ ) — length of the sequence which Petya received for his birthday. Second line of the input contains bracket sequence of length $ n $ , containing symbols "(" and ")".

输出格式

Print "Yes" if Petya can make his sequence correct moving at most one bracket. Otherwise print "No".

输入输出样例

输入样例 #1

2
)(

输出样例 #1

Yes

输入样例 #2

3
(()

输出样例 #2

No

输入样例 #3

2
()

输出样例 #3

Yes

输入样例 #4

10
)))))(((((

输出样例 #4

No

说明

In the first example, Petya can move first bracket to the end, thus turning the sequence into "()", which is correct bracket sequence. In the second example, there is no way to move at most one bracket so that the sequence becomes correct. In the third example, the sequence is already correct and there's no need to move brackets.