C. Ехаб и префиксные MEXы
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для данного массива $$$a$$$ длины $$$n$$$ найдите другой массив $$$b$$$ длины $$$n$$$ такой, что:

  • для каждого $$$i$$$ $$$(1 \le i \le n)$$$ $$$MEX(\{b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_i\})=a_i$$$.

$$$MEX$$$ множества целых чисел равен наименьшему неотрицательному целому числу, которое не принадлежит этому множеству.

Если такого массива не существует, определите это.

Входные данные

В первой строке записано целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, $$$\ldots$$$, $$$a_n$$$ ($$$0 \le a_i \le i$$$) — элементы массива $$$a$$$. Гарантируется, что $$$a_i \le a_{i+1}$$$ для $$$1\le i < n$$$.

Выходные данные

Если такого массива нет, выведите одну строку, содержащую $$$-1$$$.

В противном случае выведите одну строку, содержащую $$$n$$$ целых чисел $$$b_1$$$, $$$b_2$$$, $$$\ldots$$$, $$$b_n$$$ ($$$0 \le b_i \le 10^6$$$).

Если есть несколько ответов, выведите любой.

Примеры
Входные данные
3
1 2 3
Выходные данные
0 1 2
Входные данные
4
0 0 0 2
Выходные данные
1 3 4 0
Входные данные
3
1 1 3
Выходные данные
0 2 1
Примечание

Во втором примере допустимы другие ответы, например, $$$[1,1,1,0]$$$.