Toy Pointing Game

There are (n) toys numbered from (1) to (n). A game is played as follows:

1. Choose an index (i) with (1 \le i \le n) and point at toy (i) (this counts as one pointing for that toy).
2. Then, repeatedly, decide whether to stop. If you decide not to stop, let the currently pointed toy be (j). Then:
   • If (j=1) then you must point to toy (2).
   • If (j=n) then you must point to toy (n-1).
   • Otherwise, you may choose either toy (j-1) or toy (j+1) to point at.

Each time a toy is pointed at (including the initial pointing) its counter increases by one. In the end, a nonnegative integer sequence (a_1,a_2,\dots,a_n) is obtained. We say that the game generates the sequence (a).

Given a sequence (a_1,a_2,\dots,a_n) of nonnegative integers, determine whether there exists a valid game which generates this sequence.

Important notes:

A necessary and sufficient condition for a sequence (a) to be generated by a valid game is as follows. Let (L) be the smallest index and (R) the largest index with (a_i>0). Then, a valid sequence must satisfy:

1. For every index outside the interval ([L,R]) the value is (0).
2. The set of visited toys (indexes (L) through (R)) is contiguous (i.e. (a_i>0) for all (L \le i \le R)).
3. If (L = R) (only one toy is visited), then (a_L) must equal (1).
4. If (L < R) (more than one toy is visited), let the two endpoints (a_L) and (a_R) correspond to the two (and only two) endpoints of the walk. In any walk on a line with adjacent moves, the two endpoints appear one more time than the other (internal) toys. Hence, (a_L) and (a_R) must be odd, and every index (i) with (L < i < R) must have an even count.
5. In addition, for every adjacent pair (i) and (i+1) with (L \le i < R) the difference (|a_i - a_{i+1}|) cannot exceed (1).

If all these conditions hold, then the answer is “YES”; otherwise, it is “NO".

This problem can be solved by checking the above properties.

inputFormat

The first line contains an integer \(n\) (with \(n \ge 1\)), the number of toys.

The second line contains \(n\) nonnegative integers \(a_1,a_2,\dots,a_n\) separated by spaces, where \(a_i\) is the number of times toy \(i\) is pointed at.

outputFormat

Output a single line containing either YES or NO (without quotes) indicating whether there exists a legal game that can generate the given sequence.

sample

3
1 2 1

YES