Codeforces Global Round 18 |
---|
Закончено |
Вам задан массив $$$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
Название |
---|