CF1023D.Array Restoration

Initially there was an array $a$ consisting of $n$ integers. 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$. The order of the queries couldn't be changed and all $q$ queries were applied. It is also known that every position from $1$ to $n$ got covered by at least one segment.

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. However, we decided that it will come too easy for you.

So the enhancement we introduced to it is the following. Some set of positions (possibly empty) in this array is selected and values of elements on these positions are set to $0$.

Your task is to check if this array can be obtained by the aforementioned queries. Also if it can be obtained then restore this array.

If there are multiple possible arrays then print any of them.

最初有一个由 $n$ 个整数组成的数组 $a$，其位置编号为 $1$ 到 $n$。

对该数组恰好执行了 $q$ 次查询。在第 $i$ 次查询中，选择某个区间 $(l_i, r_i)$（满足 $1 \le l_i \le r_i \le n$），并将位置 $l_i$ 到 $r_i$（含端点）上所有元素的值修改为 $i$。查询的顺序不可更改，且全部 $q$ 次查询均被依次应用。此外，已知从位置 $1$ 到 $n$ 的每一个位置至少被某个区间覆盖过一次。

我们本可以向你提出这样一个问题：判断某个给定的数组（由 $n$ 个取值范围为 $1$ 到 $q$ 的整数组成）是否能通过上述查询过程得到。然而，我们认为这个问题对你而言过于简单。

因此，我们对此问题做了如下增强：该数组中某一部分位置（可能为空）被选中，并将这些位置上的元素值设为 $0$。

你的任务是判断该数组是否能通过上述查询过程得到；若可以，则恢复出这个原始数组。

如果存在多个可能的原始数组，输出任意一个即可。

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$.

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）—— 分别表示数组的元素个数以及在其上执行的查询次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le q$）—— 表示最终得到的数组。若某个位置 $j$ 上的元素值为 $0$，则该位置上的元素值可以是 $1$ 到 $q$ 中的任意整数。

Print "YES" if the array $a$ can be obtained by performing $q$ queries. Segments $(l_i, r_i)$ $(1 \le l_i \le r_i \le n)$ are chosen separately for each query. Every position from $1$ to $n$ should be covered by at least one segment.

Otherwise print "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$. This array should be obtainable by performing exactly $q$ queries.

If there are multiple possible arrays then print any of them.

如果数组 $a$ 可以通过执行 $q$ 次查询得到，则输出 "YES"。每次查询独立地选择一个区间 $(l_i, r_i)$（其中 $1 \le l_i \le r_i \le n$）。位置 $1$ 到 $n$ 中的每一个都必须被至少一个区间覆盖。

否则输出 "NO"。

若存在某个数组可被如此获得，则在第二行输出 $n$ 个整数——第 $i$ 个数应等于结果数组的第 $i$ 个元素，且其值应在 $1$ 到 $q$ 之间。该数组必须能通过恰好执行 $q$ 次查询得到。

若存在多个可能的数组，输出任意一个即可。

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)$.

The third example showcases the fact that the order of queries can't be changed, you can't firstly set $(1, 3)$ to $6$ and after that change $(2, 2)$ to $5$. The segment of $5$ should be applied before segment of $6$.

There is a lot of correct resulting arrays for the fourth example.

在第一个例子中，你也可以将 $0$ 替换为 $1$，但不能替换为 $3$。

在第二个例子中，在查询 $10$（此时区间为 $(1, 3)$）之前，选择哪些区间实际上并不重要。

第三个例子说明了查询顺序不可更改：你不能先将区间 $(1, 3)$ 设为 $6$，再将区间 $(2, 2)$ 改为 $5$；值为 $5$ 的区间的操作必须在值为 $6$ 的区间的操作之前执行。

第四个例子存在大量合法的最终数组。