Array Restoration
Contest: Codeforces Round 504 (rated, Div. 1 + Div. 2, based on VK Cup 2018 Final)
Difficulty rating: 1700
Tags: constructive algorithms, data structures

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
4 3
1 0 2 3

Example output:
YES
1 2 2 3

Example input:
3 10
10 10 10

Example output:
YES
10 10 10

Editorial:
Let's firstly solve the problem as if there are no zeroes in the given array. Let $$$l_i$$$ be the leftmost occurrence of $$$i$$$ in the array and $$$r_i$$$ be the rightmost occurrence of $$$i$$$. The main observation is that you can choose segments $$$(l_i; r_i)$$$ for the corresponding queries and this sequence will be correct if and only if there exists any answer for the given array. If there is no occurrence of some value in the array then you can put the segment for it under the segment of some greater value. If there is no occurrence of $$$q$$$ in the array then the answer doesn't exist.
For sure, segment $$$(l_i, r_i)$$$ is the minimum segment you can choose. You can expand it in both directions but it will never matter: these positions either will get covered by the segments of greater values or will replace the smaller values with $$$i$$$ (and turn YES to NO if the answer existed). Finally, each position will be covered as each element is a left bound of a segment, a right bound of a segment or just covered by the segment of its value.
That problem can be solved with any data structure that allows you to assign values on segment and get the value of every position (segment tree, sqrt decomposition).
However, all the queries are performed offline (the resulting values are only needed after the queries) and the operation can be replaced with assigning maximum of the current value of element and the value of the query.
This can also be done using set. For each position you should keep the segments which start there and end there. For each segment $$$(l_i, r_i)$$$ you push $$$i$$$ to the list for $$$l_i$$$ and push $$$i$$$ to the list for $$$r_i$$$. Now you iterate from $$$1$$$ to $$$n$$$, when entering $$$i$$$ you add all values of opening segments to the set, assign the element at position $$$i$$$ the maximum value of the set and remove all the values of closing segments from the set. The complexity of this algorithm is $$$O(n \log q)$$$.
This algorithm can be easily applied to the problem with zeroes in the array. At the beginning you fill the resulting array with ones. After you performed the algorithm with set on the values from $$$1$$$ to $$$q$$$, while constructing the segments from the non-zero elements of the given array, you check if the values you assigned are less or equal than the corresponding values of the given array. If that holds then the resulting array is already the correct one. Otherwise the answer doesn't exist. The only corner case there is if no value $$$q$$$ was in array and there were some zeroes. That way you should just change any zero to $$$q$$$.
Overall complexity: $$$O(n \log q)$$$.