Problem C
Balancing Act

6–7 unbalanced parentheses

One of our methods of decrypting information involves using a key composed entirely of balanced parentheses. However, an AI Overlord strike on one of our locations resulted in damage to our server that stores our keys. Some of the data was lost, the lost parentheses being overwritten with star characters.

Given a parenthetical string (a string consisting only of open and closed parenthesis ‘(’, ‘)’) there are well documented solutions for determining if it is a valid parenthesis sequence.

A valid parenthetical string is one that is balanced, meaning that each open parenthesis has a corresponding closed parenthesis later in the string and each closed parenthesis has a corresponding open parenthesis earlier in the string.

For example, the string “(()(()))" would be balanced, while “(()" and “)" would not be balanced (Note that an empty string would also be balanced in this case).

However, the parenthetical string you are given will be corrupted, with perhaps some of the characters replaced with ‘*’ characters. Your task is to determine if the string you received could have come from a valid parenthesis sequence. In other words, can you replace each ‘*’ with either a ‘(’ or a ‘’)’ (individually, not collectively) and end up with a balanced parenthetical string?

Input

The first line of input contains an integer $n (0 \leq n \leq 20)$, indicating the length of the string. The next line will contain a string of length $n$ consisting only of the characters ‘(’, ‘)’, and ‘*’.

Output

If a valid assignment exists, output YES, otherwise, output NO.

Explanation of sample output

The first sample should output YES since replacing the lone ‘*’ with ‘(’ leads to “()()" which is balanced. The second should output NO since no combination of ‘(’ and ‘)’ for both ‘*’ symbols leads to a balanced string. The third sample has 6 opening and 7 closing parentheses, which is unbalanced.

4
()*)

YES

7
*())()*

NO

13
(((((()))))))

NO