G. Реконструкция
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

После долгих исследований древнего шифра вы уверены, что близки как никогда к его расшифровке.

Однако для этого вам нужно восстановить массив $$$a$$$ длины $$$n$$$, который обладает некоторыми свойствами, или выяснить, что такого массива не существует.

1) Все элементы массива $$$a$$$ – целые, неотрицательные числа, не превышающие $$$10^{18}$$$. При этом все элементы массива $$$a$$$ различны.

2) Для каждого индекса $$$i$$$ от $$$1$$$ до $$$n$$$ вам известен индекс $$$j \ne i$$$ такой, что для любого $$$k$$$ $$$(k \ne i, k \ne j)$$$ выполняется $$$|a_k - a_i| \gt |a_i - a_j|$$$.

3) Среди всех массивов, соответствующих условиям $$$1$$$ и $$$2$$$, у массива $$$a$$$ максимальный элемент минимально возможный.

Если существует несколько массивов, соответствующих условиям $$$1, 2$$$ и $$$3$$$, то вы можете вывести любой из них.

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

Первая строка входных данных содержит число $$$n$$$ ($$$2 \le n \le 10^6$$$) - длину массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$j_1, j_2, \ldots, j_n\, (1 \le j \le n)$$$ — известные вам индексы $$$j$$$ для соответствующих $$$i$$$.

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

Если хоть 1 массив, соответствующий условиям $$$1, 2$$$ и $$$3$$$ существует, выведите его элементы $$$a_1, a_2, \ldots, a_n$$$ через пробел в отдельной строке.

Иначе выведите $$$-1$$$.

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