Задача X. Ближайшее число - 1

Автор:А. Кленин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:200 Мб
Выходной файл:output.txt  

Условие

Дан массив A, состоящий из N неотрицательных целых чисел.

Назовём правым (левым) соседом нулевого элемента ближайший к нему справа (слева) ненулевой элемент.

Требуется построить массив B, который получается из массива A заменой каждого нулевого элемента на его ближайшего соседа в массиве A. Если оба соседа отсутствуют либо расстояния до них равны, замена не производится (элемент остаётся нулевым).

Формат входного файла

Входной файл содержит число N, за которым следует N целых чисел — элементы массива A.

Формат выходного файла

Выходной файл должен содержать N целых чисел — элементы массива B.

Ограничения

1 ≤ N ≤ 10000, 0 ≤ Ai ≤ 10000

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
5
0 0 1 0 2
1 1 1 0 2
2
4
8 0 0 6
8 8 6 6

0.251s 0.026s 13