Предположим, дан массив a, стек s (изначально пустой) и массив b (также пустой).
Можно производить следующие операции, пока a или s непусты:
Операции можно осуществлять в произвольном порядке.
Если существует способ проделать операции в таком порядке, что массив b отсортирован в неубывающем порядке в конце процесса, то назовем массив a стек-сортируемым.
Например, [3, 1, 2] — стек-сортируемый, потому что 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 qi = pi, and qk > pk). Запрещено как-то переставлять или менять первые k элементов.
Выведите лексикографически максимальную перестановку p, которую можно получить.
Если ответа не существует, то выведите -1.
В первой строке записаны два целых числа n и k (2 ≤ n ≤ 200000, 1 ≤ k < n) — размер желаемой перестановки и количество элементов, которые уже заданы.
Во второй строке записаны k чисел p1, p2, ..., pk (1 ≤ pi ≤ n) — первые k элементов перестановки p. Эти числа попарно различны.
Если возможно восстановить стек-сортируемую перестановку p размера n такую, что первые k элементов перестановки p совпадают с заданными, выведите максимальную лексикографически из таковых.
В противном случае выведите -1.
5 3
3 2 1
3 2 1 5 4
5 3
2 3 1
-1
5 1
3
3 2 1 5 4
5 2
3 4
-1
Название |
---|