Stack Sorting
Contest: Educational Codeforces Round 35 (Rated for Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, data structures, greedy, implementation

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:

1. Remove 3 from a and push it into s;
2. Remove 1 from a and push it into s;
3. Remove 1 from s and append it to the end of b;
4. Remove 2 from a and push it into s;
5. Remove 2 from s and append it to the end of b;
6. 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 qi = pi, and qk > pk). 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 format:
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 p1, p2, ..., pk (1 ≤ pi ≤ n) — the first k elements of p. These integers are pairwise distinct.

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

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

Example input:
5 3
3 2 1

Example output:
3 2 1 5 4

Example input:
5 3
2 3 1

Example output:
-1

Editorial:
Let's denote A(l, r) as some stack-sortable array which contains all integers from l to r (inclusive).
We can see that if the first element of A(l, r) is x, then A(l, r) = [x] + A(l, x - 1) + A(x + 1, r), where by  +  we mean concatenation of arrays. It's easy to prove this fact: if the first element is x, then we have to store it in the stack until we have processed all elements less than x, so in A(l, r) no element that is greater than x can precede any element less than x.
This way we can represent the prefix we are given. For example, if n = 7, k = 3 and prefix is [6, 3, 4], then we can rewrite the permutation we have to obtain as:
A(1, 7) = [6] + A(1, 5) + A(7, 7) = [6] + [3] + A(1, 2) + A(4, 5) + A(7, 7) = [6] + [3] + [1] + A(2, 2) + A(4, 5) + A(7, 7).
So the unknown suffix is a contatenation of some stack-sortable arrays. It's easy to see that if an array is sorted in non-increasing order, then it is stack-sortable. So we can replace each block A(x, y) with an array [y, y - 1, y - 2, ..., x].
If during rewriting the given prefix we obtain some impossible situation (for example, when n = 7 and given prefix is [6, 7], we have [6] + A(1, 5) + A(7, 7) and 7 can't be the beginning of A(1, 5)), then answer is  - 1.