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

Starter code:

Solutions:
import sys

#f = open('input', 'r')
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])))


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")
        return

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




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

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

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

# https://codeforces.com/problemset/problem/911/E

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
                
            # len(p)=0
            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
 
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])))