Prefix table?

Let s be a string of size n. For each 0 ≤ 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₈= "aab", the longest proper
prefix and proper suffix of s₈= "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 ≤ n ≤ 10⁵ and 0 ≤ 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

© Jutge.org, 2006–2026.
https://jutge.org
