Prefix table?

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.

Problem information

Author: Salvador Roura
Event: Vint-i-quatrè Concurs de Programació de la UPC - Final
Date: 2026-10-07

Generation: 2026-10-03T13:38:25.065Z