CF911E Stack Sorting
Description
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 $ ip_{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 Format
N/A
Output Format
N/A