CF911E Stack Sorting

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.

N/A

N/A