#613 Loose Contact

Statement

Statement language

While typing a bracket sequence, you discover that your keyboard has a loose contact. Each time you press a key, the keyboard enters the corresponding character either once or twice consecutively. This may vary from one keypress to another. A keypress never produces no character or a different character.

You are given the bracket sequence $S$ left on the screen. Determine whether the sequence you originally intended to type, obtained by recording exactly one character for each keypress in order, could have been a regular bracket sequence. You do not know which keypresses produced duplicate characters, and it is possible that none did.

A regular bracket sequence is defined as follows:

The empty string is a regular bracket sequence.
If $A$ is a regular bracket sequence, surrounding $A$ with ( and ) also produces a regular bracket sequence.
If $A$ and $B$ are regular bracket sequences, their concatenation $AB$ is also a regular bracket sequence.

Input

The first line contains the length $N$ of the sequence left on the screen.

The second line contains the bracket sequence $S$ of length $N$ .

Output

Print YES if the sequence you originally intended to type could have been a regular bracket sequence, or NO otherwise.

Constraints

$1 \le N \le 1\,000\,000$
$S$ consists only of ( and ).

Samples

Sample 1

Input

3
(()

Output

YES

In the first example, the intended sequence could have been (). If only the first keypress produced the character twice, the sequence left on the screen would be (().

Sample 2

Input

4
()))

Output

In the second example, the opening bracket key must have been pressed exactly once, while the closing bracket key must have been pressed at least twice. Therefore, the intended sequence cannot have been a regular bracket sequence.

Sample 3

Input

8
()))((()

Output

In the third example, the sequence on the screen contains equal numbers of opening and closing brackets. However, producing the three closing brackets after the first opening bracket requires at least two presses of the closing bracket key, so no regular bracket sequence can be recovered.