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.