E. Сортировка стеком
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Предположим, дан массив 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 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