10881088 SUSTech Online Judge
Problem 1088 --sort by a stack

1088: sort by a stack

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 13  Solved: 5
[Submit][Status][Web Board]

Description

Give you an array A, a stack S (initially empty) and an array B(also initially empty).
If at least one of A or s is empty, you can do some operations(op1(a is not empty) or op2(s is not empty)):
op1:push the first element into S, delete it from A;
op2:S pops, append the poped element to the end of B.
You can do these operations in any order you like.
If there exists a way to perform the operations such that array B is sorted in non-descending order in the end, then we say it is sortable.

For example, [3, 1, 2] is sortable, because B will be sorted if we perform the following operations:
op1->op1->op2->op1->op2->op2
After all these op series B = [1, 2, 3], so [3, 1, 2] is sortable. But [2, 3, 1] is not.

There are T test cases,for each case:
You are given an integer n;
You are given k first elements of some permutation p of size n.
You have to restore the remaining n - k elements of this permutation so it is sortable. 
If there are multiple answers, choose the answer q that for any other answer p, there does not exist some integer k such that for every i < k , qi = pi, and qk > pk.
The first k elements could not change.
If it is sortable, print the answer.
Otherwise, output -1.

Input

The first line contans an integer T(1<=T<=20), which is the number of test cases. Then there will be 2*T lines.

For the T cases:
Each case's 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.
Each case's second line contains k integers p1, p2, ..., pk (1 ≤ pi ≤ n) — the first k elements of p. These integers are pairwise distinct.

Output

If it is possible to restore a sortable permutation p of size n, print the desired permutation.

Otherwise print -1.

Sample Input

2
5 3
3 2 1
5 3
2 3 1

Sample Output

3 2 1 5 4 
-1

HINT

Source

 

[Submit][Status]