E. Neighbor Reports
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Trida placed $$$n$$$ cards in a circle. The cards contain every integer from $$$1$$$ to $$$n$$$ exactly once, but their order is hidden.

For each position $$$i$$$, the judging team reports how many of the two neighboring cards contain a value smaller than the card at position $$$i$$$. Positions $$$1$$$ and $$$n$$$ are neighbors.

Given all reports, determine whether at least one circular ordering of the cards could produce them.

Input

The first line contains one integer $$$n$$$ ($$$3 \le n \le 2 \times 10^5$$$).

The second line contains $$$n$$$ integers $$$r_1, r_2, \ldots, r_n$$$ ($$$0 \le r_i \le 2$$$), where $$$r_i$$$ is the report for position $$$i$$$.

Output

Print YES if the reports can be produced by a permutation of $$$1,2,\ldots,n$$$ around the circle. Otherwise, print NO.

Examples
Input
3
0 1 2
Output
YES
Input
3
1 1 1
Output
NO
Note

In the first example, the circular values $$$1,2,3$$$ produce reports $$$0,1,2$$$.