River Jumping
题目描述
有一条宽度为 $N$ 的河上,小 D 位于坐标为 $0$ 的河岸上,他想到达坐标为 $N$ 的河岸上后再回到坐标为 $0$ 的位置。在到达坐标为 $N$ 的河岸之前小 D 只能向坐标更大的位置跳跃,在到达坐标为 $N$ 的河岸之后小 D 只能向坐标更小的位置跳跃。在河的中间有 $M$ 个岩石,小 D 希望能跳到每个岩石上恰好一次。由于小 D 的跳跃能力太强,小 D 的跳跃长度有个下限 $S$,但没有上限。现在请你判断他是否能够完成他的目标。
输入输出格式
输入格式
第一行输入两个整数 $N,M,S$,分别表示河的宽度,岩石的数量和跳跃长度的下限。
第二行输入 $M$ 个整数,分别表示 $M$ 个岩石的坐标 $w_1,w_2,\cdots,w_N$。保证 $\{w_i\}$ 为递增序列。
输出格式
如果小D可以完成他的目标,第一行输出 `YES`,第二行输出 $M+2$ 个数,依次表示小D跳到的石头编号。特殊的,坐标为 $0$ 的河岸编号为 $0$,坐标为$N$的河岸标号为 $M+1$ 。如果有多种解法,允许输出任意一种。
如果小 D 不能完成他的目标,第一行输出 `NO`。
输入输出样例
输入样例 #1
6 1 3
3
输出样例 #1
YES
1 2 0
输入样例 #2
6 2 2
2 4
输出样例 #2
YES
2 3 1 0
输入样例 #3
5 2 3
2 3
输出样例 #3
NO
说明
对于全部数据,保证 $1 \le N,S \le 100000$,$0 \le M < N$,$1 \le w_i < N$。