Задача . E. Сортировка стеком

Предположим, дан массив a, стек s (изначально пустой) и массив b (также пустой).

Можно производить следующие операции, пока a или s непусты:

• Взять первый элемент a, положить его на верхушку s и удалить из a (если a не пустой);
• Взять элемент с верхушки s, добавить его в конец массива b и удалить из s (если s не пустой).

Операции можно осуществлять в произвольном порядке.

Если существует способ проделать операции в таком порядке, что массив b отсортирован в неубывающем порядке в конце процесса, то назовем массив a стек-сортируемым.

Например, [3, 1, 2] — стек-сортируемый, потому что b будет отсортированным после следующих операций:

1. Удалить 3 из a и положить на верхушку s;
2. Удалить 1 из a и положить на верхушку s;
3. Удалить 1 из s и добавить в конец b;
4. Удалить 2 из a и положить на верхушку s;
5. Удалить 2 из s и добавить в конец b;
6. Удалить 3 из s и добавить в конец b.

После всех операций b = [1, 2, 3], поэтому [3, 1, 2] — стек-сортируемый. [2, 3, 1] — не стек-сортируемый.

Заданы первые k элементов некоторой перестановки p размера n (напоминаем, что перестановка размера n — это такой массив размера n, где каждое число от 1 до n встречается ровно один раз). Необходимо восстановить оставшиеся n - k элементов этой перестановки, так чтобы она стала стек-сортируемой. Если существует несколько ответов, то выберите такой, что p лексикографически максимальна (массив q лексикографически больше массива p тогда и только тогда, когда существует такое целое число k, что для всех i < k q_i = p_i, and q_k > p_k). Запрещено как-то переставлять или менять первые k элементов.

Выведите лексикографически максимальную перестановку p, которую можно получить.

Если ответа не существует, то выведите -1.