← 返回题目列表

Codeforces · 798/E

E. 迈克和排列代码

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

Mike 发现了一种新的排列编码方法。如果他有一个排列 P = [p1, p2, ..., pn],他将按以下方式对其进行编码:

用 A = [a1, a2, ..., an] 表示长度为 n 的序列,它将表示排列的代码。对于从 1 到 n 的每个 i,他将依次选择最小的未标记 j (1 ≤ j ≤ n),使得 pi < pj 并将数字 j 分配给 ai(换句话说,他执行 ai = j)并标记 j。如果没有这样的 j,他将给 ai 分配数字 - 1(他执行 ai = - 1)。

Mike 忘记了他原来的排列,但他记得它的代码。您的任务很简单:找到任何排列,使其代码与 Mike 的原始排列的代码相同。

您可以假设始终存在至少一种有效排列。

输入

第一行包含单个整数 n (1 ≤ n ≤ 500 000) — 排列的长度。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (1 ≤ ai ≤ n 或 ai = - 1) — Mike 排列的代码。

您可以假设 A 中的所有正值都不同。

输出

在第一行也是唯一一行中打印 n 个数字 p1, p2, ..., pn (1 ≤ pi ≤ n) — 与给定的代码具有相同代码的排列 P。请注意,排列中的数字是不同的。

示例

输入 #1

6
2 -1 1 5 -1 4

输出 #1

2 6 1 4 5 3

输入 #2

8
2 -1 4 -1 6 -1 8 -1

输出 #2

1 8 2 7 3 6 4 5

注意

对于第一个示例的排列:

i = 1,最小 j 为 2,因为 p2 = 6 > p1 = 2。

i = 2,没有 j,因为 p2 = 6 是排列中最大的元素。

i = 3,最小 j 为 1,因为 p1 = 2 > p3 = 1。

i = 4,最小的 j 是 5(2 已标记),因为 p5 = 5 > p4 = 4。

i = 5,没有j,因为2已经被标记了。

i = 6,最小 j 为 4,因为 p4 = 4 > p6 = 3。