AT_yahoo_procon2018_final_d LCP(prefix,suffix)

现有由非负整数组成的长度为N的数列l 请判断满足以下条件的长度为N的文字列s是否存在。并且，文字的种类数不限。 条件：对于1以上N以下的各整数i， s[1:i]s[1:i] 与 $s[N−i+1:N]$ 的最长公共头子串的长度为 l_il i ​ ​

i ​ ​

注释： s[i,j](i≤j)s[i,j](i≤j)指s文字列的第i项开始至第j项的部分文字列。例如:s＝ABCBC，t＝ABD时，最长公共头子串为AB，s＝ABC，t＝BCD时最长共通接头子串为空。 制约： 1≤N≤3*10^5 0≤l(i)≤i 给出的输入皆为整数 例解1： 例如文字列aba满足条件 例解2： 虽然长度为2的文字列有重复aa来表示的文字列和形如ab的由2个文字组成的文字列，但两者皆不满足条件 翻译者：朝阳的二愣子

### 注釈 - $ 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 $ - 与えられる入力は全て整数 ### Sample Explanation 1 \- 例えば `aba` という文字列が条件を満たします。 ### Sample Explanation 2 \- 長さ $ 2 $ の文字列は `aa` のような同じ文字の繰り返しで表せる文字列と、`ab` のような異なる $ 2 $ つの文字からなる文字列がありますが、どちらも条件を満たしません。