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

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

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.


-----Examples-----
Input
4 3
1 0 2 3

Output
YES
1 2 2 3

Input
3 10
10 10 10

Output
YES
10 10 10 

Input
5 6
6 5 6 2 2

Output
NO

Input
3 5
0 0 0

Output
YES
5 4 2



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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Constructive algorithms


Solutions:
import sys
(n, q) = list(map(int, input().split()))
a = list(map(int, input().split()))
l = len(a)
zeros = []
last = dict()
cur_max = 0
last_max = 1
stack = []
for i in range(l - 1, -1, -1):
	if a[i] == 0:
		zeros.append(i)
	elif a[i] not in last:
		last[a[i]] = i
for i in range(l):
	if a[i] == 0:
		a[i] = max(cur_max, 1)
	elif a[i] > cur_max and last[a[i]] != i:
		stack.append(cur_max)
		cur_max = a[i]
	elif cur_max != 0 and i == last[cur_max]:
		cur_max = stack.pop()
	elif a[i] < cur_max:
		print('NO')
		return
if q > max(a):
	if zeros:
		print('YES')
		a[zeros[0]] = q
		print(*a)
	else:
		print('NO')
elif q == max(a):
	print('YES')
	print(*a)
elif q < max(a):
	print('NO')


oo = int(1000000000.0)
maxN = int(200000.0 + 10)
rmq = [[0 for i in range(20)] for j in range(maxN)]
a = [0] * maxN
ans = [0] * maxN
lst = [0] * maxN
nxt = [0] * maxN
check = [False] * maxN

def get(lef, rig):
	len = rig - lef + 1
	pw2 = 0
	while 1 << pw2 + 1 <= len:
		pw2 += 1
	return min(rmq[lef][pw2], rmq[rig - (1 << pw2) + 1][pw2])
(n, q) = (int(s) for s in input().split())
inp = input().split()
flag = False
for i in range(1, n + 1):
	a[i] = int(inp[i - 1])
	if a[i] == q:
		flag = True
	if a[i] == 0:
		a[i] = oo
if flag == False:
	for i in range(1, n + 1):
		if a[i] == oo:
			a[i] = q
			flag = True
			break
for i in range(1, n + 1):
	for j in range(0, 19):
		rmq[i][j] = oo
for i in range(n, 0, -1):
	rmq[i][0] = a[i]
	for j in range(0, 18):
		if i + (1 << j) <= n:
			rmq[i][j + 1] = min(rmq[i][j], rmq[i + (1 << j)][j])
for i in range(1, n + 1):
	if a[i] < oo and check[a[i]] == False:
		lst[a[i]] = i
		check[a[i]] = True
for i in range(1, maxN):
	check[i] = False
for i in range(n, 0, -1):
	if a[i] < oo and check[a[i]] == False:
		tmp = get(lst[a[i]], i)
		if tmp < a[i] or flag == False:
			print('NO')
			exit()
		nxt[a[i]] = i
		check[a[i]] = True
cur = [0]
for i in range(1, n + 1):
	if a[i] < oo:
		ans[i] = a[i]
		if lst[a[i]] == i:
			cur.append(a[i])
		if nxt[a[i]] == i:
			cur.pop()
	elif len(cur) > 1:
		ans[i] = cur[-1]
for i in range(2, n + 1):
	if ans[i] == 0:
		ans[i] = ans[i - 1]
for i in range(n - 1, 0, -1):
	if ans[i] == 0:
		ans[i] = ans[i + 1]
print('YES')
for i in range(1, n + 1):
	print(ans[i])


import sys

def check(a, b, x, y):
	if y == -1 or b == -1:
		return True
	if b < x:
		return True
	if a > y:
		return True
	if a < x and b > y:
		return True
	return False
(n, q) = list(map(int, input().split(' ')))
array = list(map(int, input().split(' ')))
first = [n + 1 for i in range(q + 1)]
last = [-1 for i in range(q + 1)]
first_after = [n + 1 for i in range(q + 1)]
b = True
for i in range(n):
	j = array[i]
	first[j] = min(i, first[j])
	if j > 1:
		if first[j - 1] < last[j] and last[j - 1] > last[j]:
			b = False
	last[j] = max(i, last[j])
for i in range(1, q):
	b &= check(first[i], last[i], first[i + 1], last[i + 1])
if not b or first[0] == first[q]:
	print('NO')
else:
	print('YES')
	if last[q] == -1:
		array[last[0]] = q
	x = iter(array)
	for i in range(1, n):
		if array[i] == 0:
			array[i] = array[i - 1]
		j = n - 1 - i
		if array[j] == 0:
			array[j] = array[j + 1]
	print(' '.join(map(str, array)))


def readNums(type=int):
	return list(map(type, input().split()))

def solve():
	(n, q) = readNums()
	arr = readNums()
	f = set()
	p = None
	for i in range(n):
		if not arr[i]:
			continue
		if arr[i] in f:
			return None
		if p is None:
			p = arr[i]
		else:
			if arr[i] < p:
				f.add(p)
			p = arr[i]
	if 0 not in arr:
		if q > max(arr):
			return None
		return arr
	if q not in arr:
		i = 0
		while i < n and arr[i]:
			i += 1
		while i < n and (not arr[i]):
			arr[i] = q
			i += 1
	i = 0
	while i < n and (not arr[i]):
		arr[i] = 1
		i += 1
	if i == n:
		return arr
	p = arr[i]
	i += 1
	while i < n:
		if not arr[i]:
			arr[i] = p
		else:
			p = arr[i]
		i += 1
	return arr
a = solve()
if a is None:
	print('NO')
else:
	print('YES')
	for x in a:
		print(x, end=' ')


import sys, os, io
from sys import stdin
from math import log, gcd, ceil
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import math
alphabets = list('abcdefghijklmnopqrstuvwxyz')

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def si():
	return input()

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def divideCeil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def power_set(L):
	cardinality = len(L)
	n = 2 ** cardinality
	powerset = []
	for i in range(n):
		a = bin(i)[2:]
		subset = []
		for j in range(len(a)):
			if a[-j - 1] == '1':
				subset.append(L[j])
		powerset.append(subset)
	powerset_orderred = []
	for k in range(cardinality + 1):
		for w in powerset:
			if len(w) == k:
				powerset_orderred.append(w)
	return powerset_orderred

def fastPlrintNextLines(a):
	print('\n'.join(map(str, a)))

def sortByFirstAndSecond(A):
	A = sorted(A, key=lambda x: x[0])
	A = sorted(A, key=lambda x: x[1])
	return list(A)
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
else:
	input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = 1
for _ in range(t):
	(n, q) = li()
	a = li()
	d = defaultdict(lambda : 0)
	f = 0
	current = 0
	if q not in a:
		if 0 not in a:
			print('NO')
			continue
		a[a.index(0)] = q
	for i in range(n):
		if a[i] == 0:
			if i > 0:
				a[i] = a[i - 1]
	for i in range(n - 2, -1, -1):
		if a[i] == 0:
			a[i] = a[i + 1]
	d = defaultdict(lambda : 0)
	for i in range(n):
		d[a[i]] = i
	f = 0
	for i in range(1, n):
		if a[i] >= a[i - 1]:
			continue
		if d[a[i - 1]] == i - 1:
			continue
		f = 1
		break
	if f == 1:
		print('NO')
		continue
	print('YES')
	print(*a)


from math import log2
import sys
import math
(n, q) = map(int, input().split())
arr = [int(i) for i in input().split()]
dd = [-1 for i in range(q + 1)]
ddt = [-1 for i in range(q + 1)]
isq = False
iszer = False
for i in range(n):
	if arr[i] == q:
		isq = True
	if arr[i] == 0:
		iszer = True
if isq == False and iszer == False:
	print('NO')
	sys.exit()
if isq == False and iszer == True:
	for i in range(n):
		if arr[i] == 0:
			arr[i] = q
			break
for i in range(n):
	if arr[i] == 0:
		if i == 0 and n > 1 and (arr[i + 1] != 0):
			arr[i] = arr[i + 1]
		elif i != 0:
			arr[i] = arr[i - 1]
for i in range(n - 1, -1, -1):
	if arr[i] == 0:
		if i == n - 1 and n > 1 and (arr[i - 1] != 0):
			arr[i] = arr[i - 1]
		elif i != n - 1:
			arr[i] = arr[i + 1]
if arr[0] == 0:
	for i in range(n):
		arr[i] = n
for i in range(n):
	if dd[arr[i]] == -1:
		dd[arr[i]] = i
for i in range(n - 1, -1, -1):
	if ddt[arr[i]] == -1:
		ddt[arr[i]] = i
ans = True
pq = []
for i in range(n):
	if len(pq) == 0:
		pq.append(arr[i])
	if pq[len(pq) - 1] > arr[i]:
		ans = False
		break
	elif pq[len(pq) - 1] < arr[i]:
		pq.append(arr[i])
	if ddt[pq[len(pq) - 1]] == i:
		pq.pop()
if ans == False:
	print('NO')
else:
	print('YES')
	print(*arr)


from sys import stdin
(n, q) = map(int, stdin.readline().strip().split())
s = list(map(int, stdin.readline().strip().split()))
t = False
y = max(s)
if y != q:
	t = True
for i in range(1, n):
	if s[i] == 0:
		if t:
			s[i] = q
			t = False
			y = q
		else:
			s[i] = s[i - 1]
for i in range(n - 2, -1, -1):
	if s[i] == 0:
		if t:
			s[i] = q
			t = False
			y = q
		else:
			s[i] = s[i + 1]
s1 = [[-1, -1] for i in range(200005)]
for i in range(n):
	if s1[s[i]][0] == -1:
		s1[s[i]][0] = i
	s1[s[i]][1] = i
if s[0] == 0:
	print('YES')
	print((str(q) + ' ') * n)
	exit(0)
if y < q:
	print('NO')
	exit(0)
maxx = 200005
sg = [maxx for i in range(n * 2)]
for i in range(n, n * 2):
	sg[i] = s[i - n]
for i in range(n - 1, -1, -1):
	sg[i] = min(sg[i << 1], sg[(i << 1) + 1])
for i in range(200001):
	if s1[i][0] != -1:
		l = n + s1[i][0]
		r = n + s1[i][1]
		ans = maxx
		while l < r:
			if l & 1:
				ans = min(ans, sg[l])
				l += 1
			if r & 1:
				r -= 1
				ans = min(sg[r], ans)
			l >>= 1
			r >>= 1
		if ans < i:
			print('NO')
			exit(0)
print('YES')
print(*s)


import sys

class SegmentTree:

	def __init__(self, data, default=999999999999999999999999999999999, func=lambda a, b: min(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
(n, q) = map(int, input().split())
l = list(map(int, input().split()))
re = 0
ma = max(l)
if ma > q:
	print('NO')
	sys.exit()
elif ma < q:
	re = 1
for i in range(n - 2, -1, -1):
	if l[i] == 0:
		l[i] = l[i + 1]
		if re == 1:
			l[i] = q
			re = 0
for i in range(n):
	if l[i] == 0:
		l[i] = l[i - 1]
		if re == 1:
			l[i] = q
			re = 0
if l[0] == 0:
	l[0] = l[1]
if sum(l) == 0:
	re = 0
	l = [q] * n
ind = dict()
if re == 1:
	print('NO')
	sys.exit()
s = set()
f = 0
sw = SegmentTree(l)
for i in range(n):
	if l[i] not in s:
		ind.update({l[i]: i})
		s.add(l[i])
	else:
		mi = sw.query(ind[l[i]], i)
		if mi < l[i]:
			f = 1
			break
		else:
			ind[l[i]] = i
if f == 1:
	print('NO')
else:
	print('YES')
	print(*l, sep=' ')


def getRawInteger():
	return [int(x) for x in input().split()]
(n, q) = getRawInteger()
a = getRawInteger()
if n != len(a):
	raise ValueError('n is not correct.')
(l, r) = ([n] * (q + 5), [0] * (q + 5))
f = [i for i in range(n + 5)]

def getRoot(u):
	while f[u] != u:
		f[u] = f[f[u]]
		u = f[f[u]]
	return u
for i in range(n):
	l[a[i]] = min(l[a[i]], i)
	r[a[i]] = max(r[a[i]], i)
if l[q] > r[q]:
	if l[0] > r[0]:
		print('NO')
		return
	a[l[0]] = q
	f[l[0]] = getRoot(l[0] + 1)
for i in reversed(list(range(1, q + 1))):
	it = getRoot(l[i])
	while it <= r[i]:
		if a[it] < i and a[it]:
			print('NO')
			return
		a[it] = i
		f[it] = getRoot(it + 1)
		it = getRoot(it)
out = 'YES\n'
for x in a:
	if x:
		out += str(x) + ' '
	else:
		out += '1 '
print(out)


(n, q) = map(int, input().split())
arr = list(map(int, input().split()))
count_zero = arr.count(0)
count_q = arr.count(q)
if count_q == 0 and count_zero == 0:
	print('NO')
	exit()
if count_q == 0:
	for i in range(n):
		if arr[i] == 0:
			arr[i] = q
			break
for i in range(n):
	r = arr[i]
	if r > 0:
		j = i - 1
		while j >= 0 and arr[j] == 0:
			arr[j] = r
			j -= 1
		j = i + 1
		while j < n and arr[j] == 0:
			arr[j] = r
			j += 1
a = []
visited = [0 for i in range(q + 1)]
for i in range(n):
	if a and arr[i] == arr[i - 1]:
		continue
	a.append(arr[i])
counted = [0 for i in range(q + 1)]
l = len(a)
stack = []
flag = 0
for i in range(l):
	r = a[i]
	if visited[r] == 1:
		flag = 1
		break
	counted[r] += 1
	if counted[r] == 1:
		stack.append(r)
		continue
	while stack[-1] != r:
		q = stack.pop()
		if q < r:
			flag = 1
			break
		visited[q] = 1
	if flag == 1:
		break
if flag == 1:
	print('NO')
else:
	print('YES')
	if arr[0] == 0:
		arr[0] = arr[1]
	print(*arr)


def fix(N, Q, A):
	if A.count(Q) == 0:
		try:
			p = A.index(0)
			if p != -1:
				A[p] = Q
		except ValueError:
			pass
	if A[0] == 0:
		p = -1
		for i in range(1, N):
			if A[i] > 0:
				p = i
				break
		if p == -1:
			return [1] * N
		v = A[p]
		for i in range(p):
			A[i] = v
	v = -1
	for i in range(N):
		if A[i] == 0:
			assert v != -1
			A[i] = v
		else:
			v = A[i]
	return A

def findseg(segs, segi, i, j, inf):
	assert i <= j
	seg = segs[segi]
	if j - i == 0:
		return inf
	if j - i == 1:
		return seg[i]
	acc = inf
	if i % 2 == 1:
		acc = min(acc, seg[i])
		i += 1
	if j % 2 == 1:
		acc = min(acc, seg[j - 1])
		j -= 1
	return min(acc, findseg(segs, segi + 1, i // 2, j // 2, inf))

def solve(N, Q, A):
	INF = Q + 1
	A = fix(N, Q, A)
	if A.count(Q) == 0:
		return None
	segs = [list(A)]
	while len(segs[-1]) > 1:
		lseg = segs[-1]
		if len(lseg) % 2 == 1:
			lseg.append(INF)
		seg = [min(lseg[2 * i], lseg[2 * i + 1]) for i in range(len(lseg) // 2)]
		segs.append(seg)
	lefts = [N + 1] * (Q + 1)
	rights = [-1] * (Q + 1)
	for i in range(N):
		v = A[i]
		lefts[v] = min(lefts[v], i)
		rights[v] = max(rights[v], i)
	for v in range(1, Q + 1):
		if rights[v] == -1:
			continue
		left = lefts[v]
		right = rights[v]
		if findseg(segs, 0, left, right + 1, INF) != v:
			return None
	return A

def main():
	(N, Q) = [int(e) for e in input().split(' ')]
	A = [int(e) for e in input().split(' ')]
	ans = solve(N, Q, A)
	if ans is None:
		print('NO')
	else:
		print('YES')
		print(*ans)
main()


import os, sys
from io import BytesIO, IOBase
from math import inf

def cons(n, x):
	xx = n.bit_length()
	dp = [[inf] * n for _ in range(xx)]
	for i in range(n):
		dp[0][i] = inf if not x[i] else x[i]
	for i in range(1, xx):
		for j in range(n - (1 << i) + 1):
			dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + (1 << i - 1)])
	return dp

def ask(l, r, dp):
	xx1 = (r - l + 1).bit_length() - 1
	return min(dp[xx1][l], dp[xx1][r - (1 << xx1) + 1])

def main():
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	sp = cons(n, a)
	xxx = a.count(q)
	xxx1 = a.count(0)
	if xxx1:
		rrr = a.index(0)
	if a == [0] * n:
		print('YES')
		print(*[q] * n)
		return
	if not xxx and (not xxx1):
		print('NO')
		return
	pos = [-1] * (q + 1)
	fi = 0
	for (ind, i) in enumerate(a):
		if not i:
			continue
		if not fi:
			fi = i
		if pos[i] != -1:
			if ask(pos[i], ind, sp) < i:
				print('NO')
				return
		pos[i] = ind
	a[0] = fi
	for i in range(1, n):
		if not a[i]:
			a[i] = a[i - 1]
	if not xxx:
		a[rrr] = q
	print('YES')
	print(*a)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()