Вам задан массив \(a\), состоящий из \(n\) неотрицательных целых чисел.
Вам нужно заменить каждый \(0\) в \(a\) на целое число от \(1\) по \(n\). Числа \(0\) в различных позициях можно заменять на различные числа.
Назовем мерой полученного массива количество чисел \(k\) от \(1\) по \(n\), для которых выполняется следующее условие: существует пара соседних элементов, равных \(k\) (т. е. существует некоторый \(i \in [1, n - 1]\) такой, что \(a_i = a_{i + 1} = k\)). Если для какого-то числа \(k\) существует несколько пар соседей, то число все равно учитывается в мере только один раз.
Ваша задача — получить массив с максимально возможной мерой.
Выходные данные
Выведите \(n\) целых чисел, каждое из которых от \(1\) по \(n\), — массив с максимально возможной мерой.
Если существует несколько ответов, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 1 0 2
|
1 1 2 2
|
|
2
|
5
0 0 0 0 0
|
3 1 1 3 3
|
|
3
|
5
1 2 3 4 5
|
1 2 3 4 5
|
|
4
|
6
1 0 0 0 0 1
|
1 2 3 3 1 1
|
|
5
|
3
3 0 2
|
3 2 2
|
|
6
|
5
1 0 2 0 1
|
1 2 2 1 1
|
|
7
|
7
1 0 2 3 1 0 2
|
1 2 2 3 1 1 2
|