Let's suppose you have an array a, a stack s (initially empty) and an array b (also initially empty).

You may perform the following operations until both a and s are empty:

  Take the first element of a, push it into s and remove it from a (if a is not empty);  Take the top element from s, append it to the end of array b and remove it from s (if s is not empty). 

You can perform these operations in arbitrary order.

If there exists a way to perform the operations such that array b is sorted in non-descending order in the end, then array a is called stack-sortable.

For example, [3, 1, 2] is stack-sortable, because b will be sorted if we perform the following operations:

  Remove 3 from a and push it into s;  Remove 1 from a and push it into s;  Remove 1 from s and append it to the end of b;  Remove 2 from a and push it into s;  Remove 2 from s and append it to the end of b;  Remove 3 from s and append it to the end of b. 

After all these operations b = [1, 2, 3], so [3, 1, 2] is stack-sortable. [2, 3, 1] is not stack-sortable.

You are given k first elements of some permutation p of size n (recall that a permutation of size n is an array of size n where each integer from 1 to n occurs exactly once). You have to restore the remaining n - k elements of this permutation so it is stack-sortable. If there are multiple answers, choose the answer such that p is lexicographically maximal (an array q is lexicographically greater than an array p iff there exists some integer k such that for every i < k q_{i} = p_{i}, and q_{k} > p_{k}). You may not swap or change any of first k elements of the permutation.

Print the lexicographically maximal permutation p you can obtain.

If there exists no answer then output -1.


-----Input-----

The first line contains two integers n and k (2 ≤ n ≤ 200000, 1 ≤ k < n) — the size of a desired permutation, and the number of elements you are given, respectively.

The second line contains k integers p_1, p_2, ..., p_{k} (1 ≤ p_{i} ≤ n) — the first k elements of p. These integers are pairwise distinct.


-----Output-----

If it is possible to restore a stack-sortable permutation p of size n such that the first k elements of p are equal to elements given in the input, print lexicographically maximal such permutation.

Otherwise print -1.


-----Examples-----
Input
5 3
3 2 1

Output
3 2 1 5 4 
Input
5 3
2 3 1

Output
-1

Input
5 1
3

Output
3 2 1 5 4 
Input
5 2
3 4

Output
-1

Difficulty: HARD
Tags: Greedy algorithms

Data structures

Implementation

Constructive algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
(n, k) = map(int, input().split(' '))
p = list(map(int, input().split(' ')))
i = 0
s = []
cur = 1
solution = list(p)
while True:
	if len(s) > 0 and s[-1] == cur:
		cur += 1
		s.pop()
	elif i < len(p):
		if len(s) > 0 and p[i] > s[-1]:
			solution = [-1]
			break
		s.append(p[i])
		i += 1
	else:
		break
if solution[0] != -1:
	while cur <= n:
		top = s.pop() if len(s) > 0 else n + 1
		solution.extend(reversed(range(cur, top)))
		cur = top + 1
print(' '.join((str(x) for x in solution)))


import sys
(n, k) = [int(x) for x in input().split()]
a = list(reversed([int(x) - 1 for x in input().split()]))
s = []
b = []
goal = 0
used = [False] * n
for node in a:
	used[node] = True
search_from = -1
big = n - 1
res = []
while goal != n:
	while a:
		res.append(a[-1])
		s.append(a.pop())
		search_from = s[-1] - 1
		if len(s) > 1 and s[-1] > s[-2]:
			print(-1)
			return
		while s and s[-1] == goal:
			goal += 1
			s.pop()
			if s:
				search_from = s[-1] - 1
	if goal == n:
		break
	if len(s) == 0:
		while big >= 0 and used[big]:
			big -= 1
		if big == -1:
			print(-1)
			return
		used[big] = True
		a.append(big)
	else:
		while search_from >= 0 and used[search_from]:
			search_from -= 1
		if search_from == -1:
			print(-1)
			return
		used[search_from] = True
		a.append(search_from)
print(*[x + 1 for x in res])


import sys

def print_list(list):
	for i in list:
		print(i, end=' ')
	print()
(n, k) = [int(i) for i in input().split(' ')]
my_list = [int(i) for i in input().split(' ')]
stack = list()
next_pop = 1
for num in my_list:
	if stack and stack[-1] < num:
		print('-1')
		sys.exit()
	stack.append(num)
	while stack and stack[-1] == next_pop:
		stack.pop()
		next_pop += 1
while stack:
	for i in range(stack[-1] - 1, next_pop - 1, -1):
		my_list.append(i)
	next_pop = stack.pop() + 1
if next_pop > n:
	print_list(my_list)
else:
	for j in range(n, next_pop - 1, -1):
		my_list.append(j)
	print_list(my_list)


import sys
input = sys.stdin.buffer.readline
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
blocks = [[1, n]]
fail = 0
for i in range(k):
	if blocks[-1][0] <= p[i] <= blocks[-1][1]:
		if p[i] == blocks[-1][0]:
			blocks[-1][0] += 1
		elif p[i] == blocks[-1][1]:
			blocks[-1][1] -= 1
		else:
			blocks.append([blocks[-1][0], p[i] - 1])
			blocks[-2][0] = p[i] + 1
		if blocks[-1][0] > blocks[-1][1]:
			blocks.pop()
	else:
		fail = 1
if fail:
	print(-1)
else:
	for i in p[::-1]:
		blocks.append([i, i])
	while blocks:
		block = blocks.pop()
		print(*range(block[1], block[0] - 1, -1), end=' ')


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=None):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		self.mod = mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class Matrix:
	mod = 10 ** 9 + 7

	def set_mod(m):
		Matrix.mod = m

	def __init__(self, L):
		self.row = len(L)
		self.column = len(L[0])
		self._matrix = L
		for i in range(self.row):
			for j in range(self.column):
				self._matrix[i][j] %= Matrix.mod

	def __getitem__(self, item):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		return self._matrix[i][j]

	def __setitem__(self, item, val):
		if type(item) == int:
			raise IndexError('you must specific row and column')
		elif len(item) != 2:
			raise IndexError('you must specific row and column')
		(i, j) = item
		self._matrix[i][j] = val

	def __add__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] + other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __sub__(self, other):
		if (self.row, self.column) != (other.row, other.column):
			raise SizeError('sizes of matrixes are different')
		res = [[0 for j in range(self.column)] for i in range(self.row)]
		for i in range(self.row):
			for j in range(self.column):
				res[i][j] = self._matrix[i][j] - other._matrix[i][j]
				res[i][j] %= Matrix.mod
		return Matrix(res)

	def __mul__(self, other):
		if type(other) != int:
			if self.column != other.row:
				raise SizeError('sizes of matrixes are different')
			res = [[0 for j in range(other.column)] for i in range(self.row)]
			for i in range(self.row):
				for j in range(other.column):
					temp = 0
					for k in range(self.column):
						temp += self._matrix[i][k] * other._matrix[k][j]
					res[i][j] = temp % Matrix.mod
			return Matrix(res)
		else:
			n = other
			res = [[n * self._matrix[i][j] % Matrix.mod for j in range(self.column)] for i in range(self.row)]
			return Matrix(res)

	def __pow__(self, m):
		if self.column != self.row:
			raise MatrixPowError('the size of row must be the same as that of column')
		n = self.row
		res = Matrix([[int(i == j) for i in range(n)] for j in range(n)])
		while m:
			if m % 2 == 1:
				res = res * self
			self = self * self
			m //= 2
		return res

	def __str__(self):
		res = []
		for i in range(self.row):
			for j in range(self.column):
				res.append(str(self._matrix[i][j]))
				res.append(' ')
			res.append('\n')
		res = res[:len(res) - 1]
		return ''.join(res)

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
from heapq import heappush, heappop

class MinCostFlow:
	INF = 10 ** 18

	def __init__(self, N):
		self.N = N
		self.G = [[] for i in range(N)]

	def add_edge(self, fr, to, cap, cost):
		forward = [to, cap, cost, None]
		backward = forward[3] = [fr, 0, -cost, forward]
		self.G[fr].append(forward)
		self.G[to].append(backward)

	def flow(self, s, t, f):
		N = self.N
		G = self.G
		INF = MinCostFlow.INF
		res = 0
		H = [0] * N
		prv_v = [0] * N
		prv_e = [None] * N
		d0 = [INF] * N
		dist = [INF] * N
		while f:
			dist[:] = d0
			dist[s] = 0
			que = [(0, s)]
			while que:
				(c, v) = heappop(que)
				if dist[v] < c:
					continue
				r0 = dist[v] + H[v]
				for e in G[v]:
					(w, cap, cost, _) = e
					if cap > 0 and r0 + cost - H[w] < dist[w]:
						dist[w] = r = r0 + cost - H[w]
						prv_v[w] = v
						prv_e[w] = e
						heappush(que, (r, w))
			if dist[t] == INF:
				return None
			for i in range(N):
				H[i] += dist[i]
			d = f
			v = t
			while v != s:
				d = min(d, prv_e[v][1])
				v = prv_v[v]
			f -= d
			res += d * H[t]
			v = t
			while v != s:
				e = prv_e[v]
				e[1] -= d
				e[3][1] += d
				v = prv_v[v]
		return res
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import log, gcd
input = lambda : sys.stdin.buffer.readline()
mi = lambda : map(int, input().split())
li = lambda : list(mi())
(n, k) = mi()
p = li()

def check(n, p):
	stack = []
	next = 1
	used = [False for i in range(n + 1)]
	pos = 0
	while next != n + 1:
		if not used[next]:
			stack.append(p[pos])
			used[p[pos]] = True
			pos += 1
		elif not stack:
			return False
		elif stack[-1] != next:
			return False
		else:
			stack.pop()
			next += 1
	return True

def solve(n, k, P):
	p = [(P[i], i) for i in range(k)]
	p.sort()
	comp = [0 for i in range(k)]
	for i in range(k):
		(L, idx) = p[i]
		comp[idx] = i + 1
	if not check(k, comp):
		return [-1]
	p = p[::-1]
	R = n
	ans = []
	pre = -1
	flag = False
	for i in range(k):
		if not flag:
			(L, idx) = p[i]
			if L == R:
				if idx < pre:
					R = L
					break
				pre = idx
				R -= 1
				continue
			L += 1
			ans += [j for j in range(L, R + 1)]
			if idx < pre:
				R = p[i][0]
				break
			pre = idx
			R = L - 2
	else:
		ans += [j for j in range(1, R + 1)]
		ans = P + ans[::-1]
		return ans
	rest = [P[i] for i in range(pre) if P[i] <= R]
	if len(rest) != R:
		return [-1]
	elif not check(R, rest):
		return [-1]
	else:
		R = 0
	ans = P + ans[::-1]
	return ans
print(*solve(n, k, p))


import sys
(n, k) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
result = [0]
used = [0] * (n + 1)
stack = []
for x in a:
	used[x] = 1
	if result[-1] + 1 == x:
		result.append(x)
		while stack and result[-1] + 1 == stack[-1]:
			result.append(stack.pop())
	else:
		if stack and stack[-1] < x:
			print(-1)
			exit()
		stack.append(x)
stack = [n + 1] + stack + [0]
for i in range(len(stack) - 2, -1, -1):
	for j in range(stack[i] - 1, stack[i + 1], -1):
		if not used[j]:
			a.append(j)
sys.stdout.buffer.write(' '.join(map(str, a)).encode('utf-8'))


import sys
f = sys.stdin
(n, k) = map(int, f.readline().split())
(s, t) = ([n + 1], 1)
a = list(map(int, f.readline().split()))
for i in range(n):
	if i >= k:
		a += [s[-1] - 1]
	s += [a[i]]
	while len(s) != 0 and s[-1] == t:
		s.pop()
		t += 1
if len(s):
	print('-1')
else:
	print(' '.join((str(x) for x in a)))


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
d = {x: 1 for x in p}

def solve(p, d, n):
	add = []
	s = []
	for x in range(1, n + 1):
		if x not in d:
			while len(p) > 0:
				s.append(p.pop(0))
				if len(s) >= 2 and s[-1] > s[-2]:
					return (False, None)
			if len(s) == 0 or s[-1] != x:
				up = n if len(s) == 0 else s[-1] - 1
				for y in range(up, x - 1, -1):
					add.append(y)
					s.append(y)
					d[y] = 1
			s.pop()
		else:
			if len(s) == 0 or s[-1] != x:
				while len(p) > 0:
					s.append(p.pop(0))
					if len(s) >= 2 and s[-1] > s[-2]:
						return (False, None)
					if s[-1] == x:
						break
			s.pop()
	return (True, add)
ans = [x for x in p]
(flg, add) = solve(p, d, n)
if flg == False:
	print(-1)
else:
	print(' '.join([str(x) for x in ans + add]))


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest
from copy import deepcopy, copy
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()

class Searchable_BIT:

	def __init__(self, N):
		self.N = N
		self.node = [0] * (self.N + 1)
		self.cnt = 0

	def add(self, a):
		x = a
		self.cnt += 1
		while x <= self.N:
			self.node[x] += 1
			x += x & -x

	def delete(self, x):
		self.cnt -= 1
		while x <= self.N:
			self.node[x] -= 1
			x += x & -x

	def count(self, x):
		if x == 0:
			return 0
		tmp = 0
		while x > 0:
			tmp += self.node[x]
			x -= x & -x
		return tmp

	def get_maxval(self):
		return self.get_lower_i(self.cnt)

	def get_min_left(self, x):
		return self.get_lower_i(self.count(x - 1) + 1)

	def get_lower_i(self, i):
		NG = -1
		OK = self.N
		while OK - NG > 1:
			mid = (OK + NG) // 2
			if self.count(mid) >= i:
				OK = mid
			else:
				NG = mid
		return OK
(n, k) = inpl()
p = inpl()
q = deque()
res = p
rest = set(range(1, n + 1)) - set(p)
sbit = Searchable_BIT(n + 10)
for x in rest:
	sbit.add(x)
now = 1
for x in p:
	q.appendleft(x)
	while q and q[0] == now:
		q.popleft()
		now += 1
while q and q[0] == now:
	q.popleft()
	now += 1
while now != n + 1:
	pre = now
	tmp = []
	last = q[0] if q else n + 5
	for _ in range(sbit.count(last)):
		t = sbit.get_lower_i(1)
		tmp.append(t)
		sbit.delete(t)
	for x in tmp[::-1]:
		q.appendleft(x)
		res.append(x)
	while q and q[0] == now:
		q.popleft()
		now += 1
	if pre == now:
		err(-1)
if sbit.count(n + 5):
	err(-1)
else:
	print(*res)


import sys
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
setofa = set(a)
s = []
f = False
ai = 0
ans = []
for i in range(1, n + 1):
	if i in setofa:
		while ai < k and (len(s) == 0 or s[-1] != i):
			s.append(a[ai])
			ai += 1
		if len(s) == 0 or s[-1] != i:
			f = True
			break
		s.pop(-1)
		a += ans[::-1]
		ans = []
	else:
		if ai != k:
			s += a[ai:k]
			ai = k
		ans.append(i)
if f:
	print(-1)
else:
	print(' '.join(map(str, a + ans[::-1])))


import os
import sys
from io import BytesIO, IOBase
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')
from collections import Counter
import heapq
from collections import Counter
(n, k) = map(int, input().split())
t = 1
s = [n + 1]
arr = list(map(int, input().split()))
for i in range(n):
	if i >= k:
		arr += [s[-1] - 1]
	s += [arr[i]]
	while len(s) != 0 and s[-1] == t:
		s.pop()
		t += 1
if len(s):
	print(-1)
else:
	print(*arr)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	(n, k) = LI()
	a = LI()
	r = a[:]
	s = []
	m = 1
	for c in a:
		if c == m:
			m += 1
			t = len(s)
			for i in range(t - 1, -1, -1):
				if s[i] == m:
					m += 1
					t = i
				else:
					break
			if t != len(s):
				s = s[:t]
		else:
			s.append(c)
	for i in range(len(s) - 1):
		if s[i] < s[i + 1]:
			return -1
	for i in range(len(s) - 1, -1, -1):
		c = s[i]
		r += list(range(c - 1, m - 1, -1))
		m = c + 1
	r += list(range(n, m - 1, -1))
	return ' '.join(map(str, r))
print(main())


import sys
f = sys.stdin
(n, k) = list(map(int, f.readline().split()))
a = list(map(int, f.readline().split()))
aset = set(a)
st = []
failed = False
ai = 0
app = []
for p in range(1, n + 1):
	if p in aset:
		while ai < k and (len(st) == 0 or st[-1] != p):
			st.append(a[ai])
			ai += 1
		if len(st) == 0 or st[-1] != p:
			failed = True
			break
		st.pop(-1)
		a += app[::-1]
		app = []
	else:
		if ai != k:
			st += a[ai:k]
			ai = k
		app.append(p)
if failed:
	print(-1)
else:
	print(' '.join(map(str, a + app[::-1])))