{"problem":{"name":"E. Mike and code of a permutation","description":{"content":"Mike has discovered a new way to encode permutations. If he has a permutation _P_ = \\[_p_1, _p_2, ..., _p__n_\\], he will encode it in the following way: Denote by _A_ = \\[_a_1, _a_2, ..., _a__n_\\] a ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF798E"},"statements":[{"statement_type":"Markdown","content":"Mike has discovered a new way to encode permutations. If he has a permutation _P_ = \\[_p_1, _p_2, ..., _p__n_\\], he will encode it in the following way:\n\nDenote by _A_ = \\[_a_1, _a_2, ..., _a__n_\\] a sequence of length _n_ which will represent the code of the permutation. For each _i_ from 1 to _n_ sequentially, he will choose the smallest unmarked _j_ (1 ≤ _j_ ≤ _n_) such that _p__i_ < _p__j_ and will assign to _a__i_ the number _j_ (in other words he performs _a__i_ = _j_) and will mark _j_. If there is no such _j_, he'll assign to _a__i_ the number  - 1 (he performs _a__i_ =  - 1).\n\nMike forgot his original permutation but he remembers its code. Your task is simple: find **any** permutation such that its code is the same as the code of Mike's original permutation.\n\nYou may assume that there will always be at least one valid permutation.\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 500 000) — length of permutation.\n\nThe second line contains _n_ space-separated integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ _n_ or _a__i_ =  - 1) — the code of Mike's permutation.\n\nYou may assume that all positive values from _A_ are different.\n\n## Output\n\nIn first and only line print _n_ numbers _p_1, _p_2, ..., _p__n_ (1 ≤ _p__i_ ≤ _n_) — a permutation _P_ which has the same code as the given one. Note that numbers in permutation are distinct.\n\n[samples]\n\n## Note\n\nFor the permutation from the first example:\n\n_i_ = 1, the smallest _j_ is 2 because _p_2 = 6 > _p_1 = 2.\n\n_i_ = 2, there is no _j_ because _p_2 = 6 is the greatest element in the permutation.\n\n_i_ = 3, the smallest _j_ is 1 because _p_1 = 2 > _p_3 = 1.\n\n_i_ = 4, the smallest _j_ is 5 (2 was already marked) because _p_5 = 5 > _p_4 = 4.\n\n_i_ = 5, there is no _j_ because 2 is already marked.\n\n_i_ = 6, the smallest _j_ is 4 because _p_4 = 4 > _p_6 = 3.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Mike 发现了一种新的排列编码方式。如果他有一个排列 #cf_span[P = [p1, p2, ..., pn]]，他会按以下方式编码它：\n\n记 #cf_span[A = [a1, a2, ..., an]] 为一个长度为 #cf_span[n] 的序列，表示该排列的编码。对于每个 #cf_span[i] 从 #cf_span[1] 到 #cf_span[n] 依次处理，他会选择最小的未标记的 #cf_span[j]（#cf_span[1 ≤ j ≤ n]），使得 #cf_span[pi < pj]，并将 #cf_span[ai] 设为 #cf_span[j]（即执行 #cf_span[ai = j]），然后标记 #cf_span[j]。如果没有这样的 #cf_span[j]，他会将 #cf_span[ai] 设为 #cf_span[ - 1]（即执行 #cf_span[ai =  - 1]）。\n\nMike 忘记了他的原始排列，但他记得它的编码。你的任务很简单：找到 *任意一个* 排列，使其编码与 Mike 原始排列的编码相同。\n\n你可以假定至少存在一个有效的排列。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）——排列的长度。\n\n第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n] 或 #cf_span[ai =  - 1]）——Mike 排列的编码。\n\n你可以假定 #cf_span[A] 中所有正值互不相同。\n\n在第一行且仅一行中，输出 #cf_span[n] 个数字 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——一个与给定编码相同的排列 #cf_span[P]。注意排列中的数字互不相同。\n\n对于第一个示例中的排列：\n\n#cf_span[i = 1]，最小的 #cf_span[j] 是 #cf_span[2]，因为 #cf_span[p2 = 6 > p1 = 2]。\n\n#cf_span[i = 2]，不存在这样的 #cf_span[j]，因为 #cf_span[p2 = 6] 是排列中的最大元素。\n\n#cf_span[i = 3]，最小的 #cf_span[j] 是 #cf_span[1]，因为 #cf_span[p1 = 2 > p3 = 1]。\n\n#cf_span[i = 4]，最小的 #cf_span[j] 是 #cf_span[5]（#cf_span[2] 已被标记），因为 #cf_span[p5 = 5 > p4 = 4]。\n\n#cf_span[i = 5]，不存在这样的 #cf_span[j]，因为 #cf_span[2] 已被标记。\n\n#cf_span[i = 6]，最小的 #cf_span[j] 是 #cf_span[4]，因为 #cf_span[p4 = 4 > p6 = 3]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 500 000]）——排列的长度。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n] 或 #cf_span[ai =  - 1]）——Mike 排列的编码。你可以假定 #cf_span[A] 中所有正值互不相同。\n\n## Output\n\n在第一行且仅一行中，输出 #cf_span[n] 个数字 #cf_span[p1, p2, ..., pn]（#cf_span[1 ≤ pi ≤ n]）——一个与给定编码相同的排列 #cf_span[P]。注意排列中的数字互不相同。\n\n[samples]\n\n## Note\n\n对于第一个示例中的排列：#cf_span[i = 1]，最小的 #cf_span[j] 是 #cf_span[2]，因为 #cf_span[p2 = 6 > p1 = 2]。#cf_span[i = 2]，不存在这样的 #cf_span[j]，因为 #cf_span[p2 = 6] 是排列中的最大元素。#cf_span[i = 3]，最小的 #cf_span[j] 是 #cf_span[1]，因为 #cf_span[p1 = 2 > p3 = 1]。#cf_span[i = 4]，最小的 #cf_span[j] 是 #cf_span[5]（#cf_span[2] 已被标记），因为 #cf_span[p5 = 5 > p4 = 4]。#cf_span[i = 5]，不存在这样的 #cf_span[j]，因为 #cf_span[2] 已被标记。#cf_span[i = 6]，最小的 #cf_span[j] 是 #cf_span[4]，因为 #cf_span[p4 = 4 > p6 = 3]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the permutation.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be the given code, where each $ a_i \\in \\{-1\\} \\cup \\{1, 2, \\dots, n\\} $, and all positive values in $ A $ are distinct.  \n\nLet $ P = (p_1, p_2, \\dots, p_n) $ be a permutation of $ \\{1, 2, \\dots, n\\} $ to be determined.  \n\n**Constraints**  \nFor each $ i \\in \\{1, \\dots, n\\} $:  \n- If $ a_i = -1 $, then there is no unmarked $ j $ such that $ p_i < p_j $.  \n- If $ a_i = j > 0 $, then:  \n  1. $ j $ is the smallest unmarked index at step $ i $ such that $ p_i < p_j $,  \n  2. $ j $ is unmarked before step $ i $,  \n  3. $ j $ is marked after step $ i $.  \n\n**Objective**  \nFind any permutation $ P = (p_1, \\dots, p_n) $ satisfying the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF798E","tags":["constructive algorithms","data structures","graphs","sortings"],"sample_group":[["6\n2 -1 1 5 -1 4","2 6 1 4 5 3"],["8\n2 -1 4 -1 6 -1 8 -1","1 8 2 7 3 6 4 5"]],"created_at":"2026-03-03 11:00:39"}}