← 返回题目列表

AtCoder · yahoo_procon2018_final_d

D. LCP(前缀,后缀)

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

长度 小于或等于 N 由非负整数构成的数列 l 。 对于

判断是否存在满足以下条件的长度 N 的字符串 s 。另外,字符种类数没有限制。

  • 条件:1 以上 N 下面的每个整数 查找以下有关 i , 当我输入s[1:i] 和 按字典顺序比较 s[N-i+1:N] 的最长公共前缀长度是 l_i 是

注釈

  • s[i,j] (i \leq j) 是一个字符串 让它代表 s 可以得到第 i 从第一个字符开始 j 指到第几个字符的子字符串。 例如,s= ABCBC 时,s[2:4] 是 您也可以写 BCB,s[4:5] 是 您也可以写 BC 。 对于

  • 文字列 s,t 中的共同前缀中最长的那个称为 s,t 的最长公共前缀。 例如 s= ABCBC,t= ABD 的时候,最长公共前缀是 AB 变为 通过s= ABC,t= BCD 的时候最长公共前缀为空字符串。

制約

  • 1 \leq N \leq 3 \times 10^{5}
  • 0 \leq l_i \leq i
  • 给出的所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
l_1 l_2 ... l_N

出力

满足条件的长度 N 的字符串 s 存在 Yes ,否则 No 。


入力例 1

3
1 0 3

出力例 1

Yes
  • 例如 第 aba 这个字符串满足条件。

入力例 2

2
1 0

出力例 2

No
  • 长度 小于或等于 2 是 它消耗与使用 aa 这样由相同字符重复组成的字符串,以及ab 这样由不同的 2 个字符组成的字符串,都不满足条件。

入力例 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

出力例 3

Yes

入力例 4

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

出力例 4

No