G. Максимизация пар соседей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a$$$, состоящий из $$$n$$$ неотрицательных целых чисел.

Вам нужно заменить каждый $$$0$$$ в $$$a$$$ на целое число от $$$1$$$ по $$$n$$$. Числа $$$0$$$ в различных позициях можно заменять на различные числа.

Назовем мерой полученного массива количество чисел $$$k$$$ от $$$1$$$ по $$$n$$$, для которых выполняется следующее условие: существует пара соседних элементов, равных $$$k$$$ (т. е. существует некоторый $$$i \in [1, n - 1]$$$ такой, что $$$a_i = a_{i + 1} = k$$$). Если для какого-то числа $$$k$$$ существует несколько пар соседей, то число все равно учитывается в мере только один раз.

Ваша задача — получить массив с максимально возможной мерой.

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

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

Во второй строке заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le \min(n, 600)$$$) — сами элементы массива.

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

Выведите $$$n$$$ целых чисел, каждое из которых от $$$1$$$ по $$$n$$$, — массив с максимально возможной мерой.

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

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