Alternation

Input

The first line contains an integer $n$ (1 \leq n \leq 10^5) — the length of the string.

The second line contains a string $s$ of length $n$, consisting only of the characters $0$ and $1$.

Output

Print YES if it is possible to obtain the required string, or NO otherwise.

Examples

Note

In the first example, you can insert $1$ between the two original zeros and $0$ between the two original ones. The resulting string is 010101.

In the second example, after the insertions, the string will contain four zeros and two ones, so it is impossible to obtain the required string.

In the third example, you can append $1$ and then $0$ to the end of the string. The resulting string is 0101010.

Scoring

1. $15$ points — n \leq 100.

2. $25$ points — n \leq 2000.

3. $60$ points — no additional constraints.