回文构造

题目描述

长度为 $M$ 的正整数序列 $T=(T_1,T_2,\dots,T_M)$ 是回文,当且仅当对每个 $i=1,2,\dots,M$ 都有 $T_i=T_{M-i+1}$。

给定长度为 $N$ 的非负整数序列 $A = (A_1,A_2,\dots,A_N)$。判断是否存在满足以下条件的长度为 $N$ 的正整数序列 $S=(S_1,S_2,\dots,S_N)$,如果存在,求字典序最小的这样的序列。

对每个 $i=1,2,\dots,N$,以下两条同时成立:

• 序列 $(S_{i-A_i},S_{i-A_i+1},\dots,S_{i+A_i})$ 是回文。
• 如果 $2 \le i-A_i$ 且 $i+A_i \le N-1$,则序列 $(S_{i-A_i-1},S_{i-A_i},\dots,S_{i+A_i+1})$ 不是回文。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

输出格式

如果不存在满足条件的序列 $S$,输出 No。

如果存在满足条件的序列 $S$,设 $S'$ 为字典序最小的这样的序列,按以下格式输出:

Yes
S'_1 S'_2 … S'_N

样例

7
0 0 2 0 2 0 0

Yes
1 1 2 1 1 1 2

$S = (1,1,2,1,1,1,2)$ 满足条件:

• $i=1$:$(S_1)=(1)$ 是回文。
• $i=2$:$(S_2)=(1)$ 是回文,但 $(S_1,S_2,S_3)=(1,1,2)$ 不是。
• $i=3$:$(S_1,S_2,\dots,S_5)=(1,1,2,1,1)$ 是回文。
• $i=4$:$(S_4)=(1)$ 是回文,但 $(S_3,S_4,S_5)=(2,1,1)$ 不是。
• $i=5$:$(S_3,S_4,\dots,S_7)=(2,1,1,1,2)$ 是回文。
• $i=6$:$(S_6)=(1)$ 是回文,但 $(S_5,S_6,S_7)=(1,1,2)$ 不是。
• $i=7$:$(S_7)=(2)$ 是回文。

还存在其他满足条件的序列,如 $S=(2,2,1,2,2,2,1)$,但应输出字典序最小的 $(1,1,2,1,1,1,2)$。

7
0 1 2 3 2 1 0

Yes
1 1 1 1 1 1 1

7
0 1 2 0 2 1 0

No

数据范围

• $1 \le N \le 2 \times 10^5$
• $0 \le A_i \le \min\{i-1,N-i\}$
• 输入均为整数。