← 返回题目列表

Codeforces · 1615/G

G. 最大相邻对

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 非负整数。

您必须将$$$a$$$中的每个$$$0$$$替换为$$$1$$$到$$$n$$$之间的整数(等于$$$0$$$的不同元素可以用不同的整数替换)。

您获得的数组的值是从 $$$1$$$ 到 $$$n$$$ 的整数 $$$k$$$ 的个数,满足以下条件:存在一对等于 $$$k$$$ 的相邻元素(即 [1, n - 1]$$$ 中存在一些 $$$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$$$ 的整数 - 您可以获得的最大可能值的数组。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

4
1 1 0 2

输出 #1

1 1 2 2

输入 #2

5
0 0 0 0 0

输出 #2

3 1 1 3 3

输入 #3

5
1 2 3 4 5

输出 #3

1 2 3 4 5

输入#4

6
1 0 0 0 0 1

输出#4

1 2 3 3 1 1

输入 #5

3
3 0 2

输出 #5

3 2 2

输入 #6

5
1 0 2 0 1

输出 #6

1 2 2 1 1

输入#7

7
1 0 2 3 1 0 2

输出 #7

1 2 2 3 1 1 2