最初有一个由 $$$n$$$ 整数组成的数组 $$$a$$$。 Positions in it are numbered from $$$1$$$ to $$$n$$$.
Exactly $$$q$$$ queries were performed on the array. During the $$$i$$$-th query some segment $$$(l_i, r_i)$$$ $$$(1 \le l_i \le r_i \le n)$$$ was selected and values of elements on positions from $$$l_i$$$ to $$$r_i$$$ inclusive got changed to $$$i$$$.查询的顺序无法更改,并且所有 $$$q$$$ 查询均已应用。还知道从 $$$1$$$ 到 $$$n$$$ 的每个位置都被至少一个段覆盖。
We could have offered you the problem about checking if some given array (consisting of $$$n$$$ integers with values from $$$1$$$ to $$$q$$$) can be obtained by the aforementioned queries.然而,我们认为这对您来说太容易了。
因此,我们对其进行的增强如下。 Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to $$$0$$$.
你的任务是检查这个数组是否可以通过上述查询获得。 Also if it can be obtained then restore this array.
If there are multiple possible arrays then print any of them.
输入
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — the number of elements of the array and the number of queries perfomed on it.
The second line contains $$$n$$$ integer numbers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le q$$$) — the resulting array. If element at some position $$$j$$$ is equal to $$$0$$$ then the value of element at this position can be any integer from $$$1$$$ to $$$q$$$.
输出
如果可以通过执行 $$$q$$$ 查询来获取数组 $$$a$$$,则打印“YES”。段 $$$(l_i, r_i)$$$ $$$(1 \le l_i \le r_i \le n)$$$ 是为每个查询单独选择的。从 $$$1$$$ 到 $$$n$$$ 的每个位置应至少被一个段覆盖。
否则打印“NO”。
If some array can be obtained then print $$$n$$$ integers on the second line — the $$$i$$$-th number should be equal to the $$$i$$$-th element of the resulting array and should have value from $$$1$$$ to $$$q$$$.该数组应该可以通过精确执行 $$$q$$$ 查询来获取。
If there are multiple possible arrays then print any of them.
示例
输入 #1
4 3 1 0 2 3
输出 #1
YES 1 2 2 3
输入 #2
3 10 10 10 10
输出 #2
YES 10 10 10
输入 #3
5 6 6 5 6 2 2
输出 #3
NO
输入#4
3 5 0 0 0
输出#4
YES 5 4 2
注意
In the first example you can also replace $$$0$$$ with $$$1$$$ but not with $$$3$$$.
In the second example it doesn't really matter what segments to choose until query $$$10$$$ when the segment is $$$(1, 3)$$$.
第三个示例展示了查询顺序无法更改的事实,您不能首先将 $$$(1, 3)$$$ 设置为 $$$6$$$,然后将 $$$(2, 2)$$$ 更改为 $$$5$$$。 The segment of $$$5$$$ should be applied before segment of $$$6$$$.
There is a lot of correct resulting arrays for the fourth example.