D. Восстановление массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Изначально был дан массив $$$a$$$, состоящий из $$$n$$$ целых чисел. Позиции в нем пронумерованы от $$$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$$$.

Ваша задача — проверить, что такой массив мог быть получен приведенными выше запросами. Также, если мог, то восстановить этот массив.

Если существует несколько возможных массивов, то выведите любой из них.

Входные данные

В первой строке записаны два целых $$$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$$$.

Выходные данные

Выведите «YES», если массив $$$a$$$ может быть получен применением $$$q$$$ запросов. Отрезки $$$(l_i, r_i)$$$ $$$(1 \le l_i \le r_i \le n)$$$ выбираются независимо друг от друга при каждом запросе. Каждая позиция от $$$1$$$ до $$$n$$$ должна быть покрыта хотя бы одним отрезком.

В противном случае выведите «NO».

Если некоторый массив мог быть получен, то выведите $$$n$$$ целых чисел во второй строке — $$$i$$$-е число должно быть равно значению $$$i$$$-го элемента полученного массива и должно иметь значение от $$$1$$$ до $$$q$$$. Должно быть возможно получить данный массив применением ровно $$$q$$$ запросов.

Если существует несколько возможных массивов, то выведите любой из них.

Примеры
Входные данные
4 3
1 0 2 3
Выходные данные
YES
1 2 2 3
Входные данные
3 10
10 10 10
Выходные данные
YES
10 10 10
Входные данные
5 6
6 5 6 2 2
Выходные данные
NO
Входные данные
3 5
0 0 0
Выходные данные
YES
5 4 2
Примечание

В первом примере можно также заменить $$$0$$$ значением $$$1$$$, но не $$$3$$$.

Во втором примере не важно, какие отрезки выбирались до запроса $$$10$$$, при котором был запрос $$$(1, 3)$$$.

Третий пример демонстрирует тот факт, что порядок операций не может быть изменен, нельзя сначала присвоить элементы $$$(1, 3)$$$ значению $$$6$$$, и только потом $$$(2, 2)$$$ значению $$$5$$$. Отрезок для $$$5$$$ должен быть применен до отрезка для $$$6$$$.

В четвертом примере существует много корректных ответов.