Problem Description

Given a sequence $ l $ of non-negative integers of length $ N $.

Determine whether there exists a string $ s $ of length $ N $ that satisfies the following conditions. Note that there is no restriction on the number of character types.

• Condition: For each integer $ i $ between $ 1 $ and $ N $, the length of the longest common prefix of $ s[1:i] $ and $ s[N-i+1:N] $ is $ l_i $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ l_1 $ $ l_2 $ $ ... $ $ l_N $

Output Format

If there exists a string $ s $ of length $ N $ that satisfies the conditions, output Yes; otherwise, output No.

Sample Input and Output

Sample Input #1

3
1 0 3

Sample Output #1

Yes

Sample Input #2

2
1 0

Sample Output #2

No

Sample Input #3

29
1 0 3 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 0 6 1 1 1 1 0 29

Sample Output #3

Yes

Sample Input #4

18
1 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 17 18

Sample Output #4

No

Notes/Hints

Notes

• $s[i,j]\ (i\ \leq\ j)$ refers to the substring of $ s $ from the $ i $-th character to the $ j $-th character. For example, when $ s= $ ABCBC, $ s[2:4] $ is BCB and $ s[4:5] $ is BC.
• The longest common prefix of two strings $ s $ and $ t $ is the longest prefix that is common to both $ s $ and $ t $. For example, when $ s= $ ABCBC and $ t= $ ABD, the longest common prefix is AB. When $ s= $ ABC and $ t= $ BCD, the longest common prefix is the empty string.

Constraints

• $1\ \leq\ N\ \leq\ 3\ \times\ 10^{5}$
• $0\ \leq\ l_i\ \leq\ i$
• All given inputs are integers.

Sample Explanation 1

• For example, the string aba satisfies the conditions.

Sample Explanation 2

• A string of length $ 2 $ can be either a repetition of the same character like aa or a combination of two different characters like ab, but neither satisfies the conditions.

见题面 Input 部分

见题面 Output 部分