Maximum Adjacent Pairs

题意翻译

给定一个数列 $a$，你需要将所有 $a_i=0$ 的位置填上一个 $1\sim n$ 的正整数，使得数列的「值」最大。 数列的值定义为满足以下条件的 $k$ 的个数： - 存在 $i\in\Z[1,n-1]$，使得 $a_{i}=a_{i+1}=k$。 输出值最大的序列，若有多解，输出任意一个。 $0\le a\le \min(n,600)$；$0<n\le 3\times 10^5$。

题目描述

You are given an array $ a $ consisting of $ n $ non-negative integers. You have to replace each $ 0 $ in $ a $ with an integer from $ 1 $ to $ n $ (different elements equal to $ 0 $ can be replaced by different integers). The value of the array you obtain is the number of integers $ k $ from $ 1 $ to $ n $ such that the following condition holds: there exist a pair of adjacent elements equal to $ k $ (i. e. there exists some $ i \in [1, n - 1] $ such that $ a_i = a_{i + 1} = k $ ). If there are multiple such pairs for some integer $ k $ , this integer is counted in the value only once. Your task is to obtain the array with the maximum possible value.

输入输出格式

输入格式

The first line contains one integer $ n $ ( $ 2 \le n \le 3 \cdot 10^5 $ ) — the number of elements in the array. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le \min(n, 600) $ ) — the elements of the array.

输出格式

Print $ n $ integers not less than $ 1 $ and not greater than $ n $ — the array with the maximum possible value you can obtain. If there are multiple answers, print any of them.

输入输出样例

输入样例 #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