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 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:
( and ) also produces a regular bracket sequence.The first line contains the length of the sequence left on the screen.
The second line contains the bracket sequence of length .
Print YES if the sequence you originally intended to type could have been a regular bracket sequence, or NO otherwise.
( and ).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 (().
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.
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.