Prefix table? P99427

Statement

Let $s$ be a string of size $n$ . For each $0 \le i < n$ , let $s_i = s[0..i]$ , and let $p_i$ be the longest prefix of $s_i$ that is also a suffix of $s_i$ (excluding $s_i$ itself). The prefix table $P$ for $s$ is a vector of $n$ integers that stores at $P[i]$ the size of $p_i$ .

For instance, let $s$ be "aabaacaabaa". The prefix table in this case is

0 1 2 3 4 5 6 7 8 9 10

a	a	b	a	a	c	a	a	b	a	a
0	1	0	1	2	0	1	2	3	4	5

For example, $P$ [8] $=3$ corresponds to $p_8 =$ "aab", the longest proper prefix and proper suffix of $s_8=$ "aabaacaab".

As other examples, the prefix table of "zzzzzz" is $[0, 1, 2, 3, 4, 5]$ , and the prefix table of "ababa" is $[0, 0, 1, 2, 3]$ .

Given a vector of integers, could it be the prefix table of some string?

Input

Input consists of several cases, each with $n$ , followed by $P[0]$ , …, $P[n-1]$ . You can assume $1 \le n \le 10^5$ and $0 \le P[i] < n$ .

Output

For each case, print “yes” or “no” depending on whether the given numbers can define the prefix table of some string. Assume that we use an alphabet with an unlimited number of different characters.

Public test cases

Input

5  0 1 2 0 1
4  0 1 0 3
3  1 2 1
6  0 0 1 1 2 2
1  0

Output

yes
no
no
no
yes

Information

Author: Salvador Roura
Language: English
Official solutions: C++
User solutions: C++