序列重构（border）

题目描述

Y 同学是一位对字符串 Border 性质深有研究的学者。最近，他提出了一个关于逆向构造的有趣问题。

给定一个长度为 $N$ 的整数序列 $A = (A_1, A_2, \dots, A_N)$，其中每一个元素 $A_i$ 均满足 $0 \le A_i < i$。你需要构造一个长度同样为 $N$ 的正整数序列 $S = (S_1, S_2, \dots, S_N)$，使得该序列满足以下所有条件：

1. 对于所有的 $i \in [1, N]$，有 $1 \le S_i \le N$。
2. 对于所有的 $i \in [1, N]$，序列 $S$ 的前缀 $S[1 \dots A_i]$ 与序列 $S$ 前 $i$ 个元素构成的子串的后缀 $S[i - A_i + 1 \dots i]$ 完全相同。即：对于所有的 $j \in [1, A_i]$，均满足 $S_j = S_{i - A_i + j}$。
3. 在满足上述所有约束的前提下，序列 $S$ 中出现的不同元素的数量必须达到最大。
4. 在满足上述所有约束且不同元素数量最大的前提下，序列 $S$ 的字典序必须最小。

Y 同学可以轻松地解决这个问题，但他想考考你。

输入格式

第一行包含一个整数 $N$，表示序列 $A$ 的长度。

第二行包含 $N$ 个整数，第 $i$ 个整数为 $A_i$，表示题目给定的限制条件。

输出格式

输出一行 $N$ 个由空格隔开的整数，表示构造出的序列 $S$。

样例

样例输入 #1

5
0 0 1 2 3

样例输出 #1

1 2 1 2 1

样例输入 #2

11
0 0 0 0 2 1 0 0 3 0 1

样例输出 #2

1 2 3 1 2 1 1 2 3 4 1

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N \le 2 \cdot 10^5$，且对于所有的 $i \in [1, N]$，均有 $0 \le A_i < i$。

• 特殊性质 A：对于所有的 $i \in [1, N]$，保证 $A_i \le 1$。
• 特殊性质 B：对于所有的 $i \in [1, N]$，保证 $A_i \in \{0, i-1\}$。