{"problem":{"name":"C. Petya and Catacombs","description":{"content":"A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs. Catacombs consist of several rooms a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF890C"},"statements":[{"statement_type":"Markdown","content":"A very brave explorer Petya once decided to explore Paris catacombs. Since Petya is not really experienced, his exploration is just walking through the catacombs.\n\nCatacombs consist of several rooms and bidirectional passages between some pairs of them. Some passages can connect a room to itself and since the passages are built on different depths they do not intersect each other. Every minute Petya arbitrary chooses a passage from the room he is currently in and then reaches the room on the other end of the passage in exactly one minute. When he enters a room at minute _i_, he makes a note in his logbook with number _t__i_:\n\n*   If Petya has visited this room before, he writes down the minute he was in this room last time;\n*   Otherwise, Petya writes down an arbitrary non-negative integer strictly less than current minute _i_.\n\nInitially, Petya was in one of the rooms at minute 0, he didn't write down number _t_0.\n\nAt some point during his wandering Petya got tired, threw out his logbook and went home. Vasya found his logbook and now he is curious: what is the minimum possible number of rooms in Paris catacombs according to Petya's logbook?\n\n## Input\n\nThe first line contains a single integer _n_ (1 ≤ _n_ ≤ 2·105) — then number of notes in Petya's logbook.\n\nThe second line contains _n_ non-negative integers _t_1, _t_2, ..., _t__n_ (0 ≤ _t__i_ < _i_) — notes in the logbook.\n\n## Output\n\nIn the only line print a single integer — the minimum possible number of rooms in Paris catacombs.\n\n[samples]\n\n## Note\n\nIn the first sample, sequence of rooms Petya visited could be, for example 1 → 1 → 2, 1 → 2 → 1 or 1 → 2 → 3. The minimum possible number of rooms is 2.\n\nIn the second sample, the sequence could be 1 → 2 → 3 → 1 → 2 → 1.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"一位非常勇敢的探险家彼得决定探索巴黎的地下墓穴。由于彼得经验不足，他的探索仅仅是穿过墓穴的步行。\n\n地下墓穴由若干房间和连接其中某些房间对的双向通道组成。某些通道可以连接一个房间到其自身，并且由于通道建造在不同深度，它们不会相互交叉。每分钟，彼得从他当前所在的房间任意选择一条通道，并在恰好一分钟内到达通道另一端的房间。当他第 #cf_span[i] 分钟进入一个房间时，他在日志本上记录一个数字 #cf_span[ti]：\n\n最初，彼得在第 #cf_span[0] 分钟位于某个房间，他没有记录数字 #cf_span[t0]。\n\n在漫游过程中，彼得感到疲倦，丢掉了日志本并回家了。瓦西里找到了他的日志本，现在他好奇：根据彼得的日志本，巴黎地下墓穴中房间的最少可能数量是多少？\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——彼得日志本中的记录数量。\n\n第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。\n\n仅输出一行，一个整数——巴黎地下墓穴中房间的最少可能数量。\n\n在第一个样例中，彼得访问的房间序列可能是，例如 #cf_span[1 → 1 → 2]、#cf_span[1 → 2 → 1] 或 #cf_span[1 → 2 → 3]。房间的最少可能数量是 #cf_span[2]。\n\n在第二个样例中，序列可能是 #cf_span[1 → 2 → 3 → 1 → 2 → 1]。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 2·105]）——彼得日志本中的记录数量。第二行包含 #cf_span[n] 个非负整数 #cf_span[t1, t2, ..., tn]（#cf_span[0 ≤ ti < i]）——日志本中的记录。\n\n## Output\n\n仅输出一行，一个整数——巴黎地下墓穴中房间的最少可能数量。\n\n[samples]\n\n## Note\n\n在第一个样例中，彼得访问的房间序列可能是，例如 #cf_span[1 → 1 → 2]、#cf_span[1 → 2 → 1] 或 #cf_span[1 → 2 → 3]。房间的最少可能数量是 #cf_span[2]。在第二个样例中，序列可能是 #cf_span[1 → 2 → 3 → 1 → 2 → 1]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n $ be the number of log entries, and let $ t_1, t_2, \\dots, t_n $ be the sequence of timestamps recorded at each minute $ i $, where $ 0 \\leq t_i < i $.\n\nDefine $ r_i $ as the room Petya is in at minute $ i $, for $ i = 0, 1, \\dots, n $, with $ r_0 $ being the initial room (not recorded).\n\nEach entry $ t_i $ indicates that at minute $ i $, Petya wrote down the number of the room he was in at minute $ t_i $, i.e., $ r_i = r_{t_i} $.\n\nWe are to find the **minimum possible number of distinct rooms** $ |\\{r_0, r_1, \\dots, r_n\\}| $ consistent with the constraints.\n\n---\n\n### Formal Mathematical Formulation:\n\n**Given:**\n- Integer $ n \\geq 1 $\n- Sequence $ \\mathbf{t} = (t_1, t_2, \\dots, t_n) $, where $ t_i \\in \\{0, 1, \\dots, i-1\\} $\n\n**Define:**\n- A sequence of room labels $ r_0, r_1, \\dots, r_n $, where each $ r_i \\in \\mathbb{N} $ (room identifiers)\n- Constraint: For each $ i \\in \\{1, 2, \\dots, n\\} $, $ r_i = r_{t_i} $\n\n**Objective:**\nMinimize $ \\left| \\{ r_0, r_1, \\dots, r_n \\} \\right| $\n\n---\n\n### Key Insight:\n\nThe constraint $ r_i = r_{t_i} $ forces room $ i $ to be the same as room $ t_i $. Thus, the sequence defines a **functional dependency**: each $ i $ is linked to $ t_i $, forming a directed graph where each node $ i \\geq 1 $ has out-degree 1 to $ t_i $, and node $ 0 $ is the root.\n\nThis forms a **forest of trees** rooted at node 0 (or possibly other components if $ t_i $ points to non-zero nodes, but all paths eventually lead to 0 due to $ t_i < i $).\n\nThe number of distinct rooms is the number of **connected components** in the equivalence relation generated by $ i \\sim t_i $, where $ r_i = r_{t_i} $, and we are free to assign distinct room numbers to distinct equivalence classes.\n\nBut note: we can **choose** $ r_0 $ arbitrarily, and then all $ r_i $ are forced to equal $ r_{t_i} $. So the minimal number of rooms is the number of **distinct equivalence classes** under the relation $ i \\sim j $ if they are connected via the chain $ i \\to t_i \\to t_{t_i} \\to \\dots \\to 0 $.\n\nHowever, since the mapping $ i \\mapsto t_i $ defines a **directed tree** (actually a **functional graph** with each node pointing to a smaller index, ending at 0), the equivalence classes are determined by **when two indices point to the same chain**.\n\nBut crucially: **if two indices $ i $ and $ j $ have $ t_i = t_j $, then $ r_i = r_{t_i} = r_{t_j} = r_j $, so they must be the same room.**\n\nTherefore, the minimal number of distinct rooms is equal to the number of **distinct values in the sequence $ t_1, t_2, \\dots, t_n $**, **plus one** for the initial room $ r_0 $, **unless** $ r_0 $ is already forced to equal some $ r_i $.\n\nWait — but $ r_0 $ is **not** forced by any constraint except that $ r_1 = r_{t_1} $, and $ t_1 = 0 $, so $ r_1 = r_0 $. So in fact, **$ r_0 $ is always equal to $ r_{t_1} $** since $ t_1 = 0 $, and $ r_1 = r_0 $.\n\nThus, **$ r_0 $ is not an independent room** — it is the same as $ r_1 $, which is forced to be equal to $ r_{t_1} = r_0 $.\n\nSo the entire sequence of room assignments is determined by the constraints $ r_i = r_{t_i} $, and $ r_0 $ is just the value assigned to the root of the component.\n\nTherefore, the minimal number of distinct rooms is equal to the number of **distinct connected components** in the graph induced by the mapping $ i \\mapsto t_i $ for $ i = 1 $ to $ n $, **with node 0 as the base**.\n\nBut since every node $ i \\geq 1 $ points to some $ t_i < i $, and $ t_i \\geq 0 $, the entire graph is a **tree rooted at 0**, and the equivalence classes are determined by **which node in the path to 0 is first shared**.\n\nActually, the minimal number of rooms is equal to the number of **distinct values among $ r_0, r_1, \\dots, r_n $** under the constraint $ r_i = r_{t_i} $.\n\nWe can assign the same room number to all nodes that are forced to be equal. So the number of distinct rooms is the number of **distinct equivalence classes** under the relation generated by $ i \\sim t_i $.\n\nThis is equivalent to the number of **connected components** in the undirected graph where we connect $ i $ and $ t_i $ for each $ i = 1, \\dots, n $, **with node 0 included**.\n\nBut since the graph is a forest of trees rooted at 0 (because $ t_i < i $), the entire structure is **one connected component** if we consider undirected edges? No — because $ t_i $ can point to any smaller index, including non-zero ones, and multiple chains can merge.\n\nActually, the structure is a **directed forest** with edges $ i \\to t_i $, and since $ t_i < i $, it's a DAG with all paths leading to 0.\n\nBut in terms of **room equality**, we have $ r_i = r_{t_i} $, so all nodes in the same connected component (under undirected reachability) must have the same room.\n\nThus, the number of distinct rooms is the number of **connected components** in the undirected graph formed by edges $ \\{i, t_i\\} $ for $ i = 1 $ to $ n $, **plus node 0**.\n\nBut node 0 is always connected to all $ i $ such that $ t_i = 0 $, and recursively to others.\n\nActually, since every node $ i $ has a path to 0 (because $ t_i < i $, so by induction, $ t_i $ eventually reaches 0), **the entire graph is one connected component**?\n\nNo — consider: if $ t_1 = 0 $, $ t_2 = 0 $, $ t_3 = 1 $, then:\n\n- $ r_1 = r_0 $\n- $ r_2 = r_0 $\n- $ r_3 = r_1 = r_0 $\n\nSo all equal.\n\nBut what if $ t_1 = 0 $, $ t_2 = 1 $, $ t_3 = 2 $? Then $ r_3 = r_2 = r_1 = r_0 $ — still one room.\n\nWait — then why is the first sample answer 2?\n\nSample 1: $ n = 2 $, $ t = [0, 1] $\n\nSo:\n- $ r_1 = r_{t_1} = r_0 $\n- $ r_2 = r_{t_2} = r_1 = r_0 $\n\nSo all rooms equal → only 1 room? But sample says answer is 2.\n\nContradiction?\n\nWait — let's re-read the problem:\n\n> When he enters a room at minute #cf_span[i], he makes a note in his logbook with number #cf_span[ti]:\n\nThis means: at minute $ i $, he writes down the **room number he was in at minute $ t_i $**.\n\nSo the log entry at minute $ i $ is the **label of room $ r_{t_i} $**.\n\nBut the problem does **not** say that $ r_i = r_{t_i} $.\n\nIt says: at minute $ i $, he writes down the number of the room he was in at minute $ t_i $.\n\nSo the **log entry** $ t_i $ is the **value** of $ r_{t_i} $, not that $ r_i = r_{t_i} $.\n\nAh! Critical misinterpretation.\n\nLet me re-analyze.\n\n---\n\n### Correct Interpretation:\n\n- At minute $ i $, Petya is in room $ r_i $.\n- He writes down in his logbook: the **number** of the room he was in at minute $ t_i $, i.e., he writes $ r_{t_i} $.\n- So the logbook contains the sequence $ r_{t_1}, r_{t_2}, \\dots, r_{t_n} $.\n- But we are **given** the sequence of written numbers: $ t_1, t_2, \\dots, t_n $ — wait, no!\n\nWait, the problem says:\n\n> The second line contains $ n $ non-negative integers $ t_1, t_2, \\dots, t_n $ ($ 0 \\leq t_i < i $) — notes in the logbook.\n\nBut it says: \"he makes a note in his logbook with number $ t_i $\".\n\nSo: **the number written at minute $ i $ is $ t_i $**.\n\nBut earlier: \"he makes a note in his logbook with number $ t_i $\", and \"when he enters a room at minute $ i $, he makes a note [...] with number $ t_i $\".\n\nAnd: \"he didn't write down number $ t_0 $\".\n\nSo: **the value written at minute $ i $ is $ t_i $**.\n\nBut what does $ t_i $ represent? The problem says: \"he makes a note in his logbook with number $ t_i $\", and \"when he enters a room at minute $ i $, he makes a note [...] with number $ t_i $\".\n\nAnd: \"he was in one of the rooms at minute 0\".\n\nSo: the logbook entry at minute $ i $ is **the room number he was in at minute $ t_i $**.\n\nBut then, the value written is **the room label at time $ t_i $**, not the time index.\n\nBut the input gives us **$ t_i $** as the value written — so **$ t_i $ is the room number** he was in at minute $ t_i $.\n\nWait — that can’t be: the room numbers are arbitrary, and $ t_i $ is given as an integer between 0 and $ i-1 $.\n\nAh! Now I see the confusion.\n\nThe problem says:\n\n> he makes a note in his logbook with number $ t_i $\n\nand then says:\n\n> The second line contains $ n $ non-negative integers $ t_1, t_2, \\dots, t_n $ ($ 0 \\leq t_i < i $) — notes in the logbook.\n\nSo: **the number written at minute $ i $ is $ t_i $**, and this number is **equal to the room number he was in at minute $ t_i $**.\n\nSo:  \nAt minute $ i $, Petya writes down the **room number** he was in at minute $ t_i $.  \nBut the value he writes is $ t_i $ (the integer given in input).  \nSo:  \n$$\nr_{t_i} = t_i\n$$\n\nWait — that would mean: the room number at minute $ t_i $ is equal to the integer $ t_i $.\n\nBut room numbers are arbitrary — we can assign them.\n\nSo the constraint is:  \nFor each $ i \\in \\{1, 2, \\dots, n\\} $, the room Petya was in at minute $ t_i $ has **label $ t_i $**.\n\nThat is:  \n$$\nr_{t_i} = t_i\n$$\n\nAnd at minute $ i $, he is in some room $ r_i $, and he writes down $ r_{t_i} = t_i $.\n\nSo the **only constraints** are:  \nFor each $ i \\in \\{1, \\dots, n\\} $, $ r_{t_i} = t_i $\n\nAdditionally, Petya moves from room to room each minute: so $ r_i $ and $ r_{i-1} $ are connected by a passage — but since we are to find the **minimum number of rooms**, and passages can be arbitrary (even self-loops), the only constraint on room transitions is that **consecutive rooms can be the same or different** — no restriction other than the logbook.\n\nSo the only hard constraints are:\n\n- $ r_{t_i} = t_i $ for each $ i = 1, 2, \\dots, n $\n\nAnd we must assign room labels $ r_0, r_1, \\dots, r_n $ such that these constraints are satisfied, and we want to minimize the number of distinct values among $ r_0, r_1, \\dots, r_n $.\n\nNote: $ t_i < i $, so $ t_i \\in \\{0, 1, \\dots, i-1\\} $, so $ r_{t_i} $ is defined.\n\nSo we have a set of equations:  \nFor each $ i \\in \\{1, \\dots, n\\} $: $ r_{t_i} = t_i $\n\nWe need to assign values to $ r_0, r_1, \\dots, r_n $ satisfying these, and minimize $ |\\{r_0, \\dots, r_n\\}| $\n\n---\n\n### Example 1: $ n=2 $, $ t = [0, 1] $\n\nConstraints:\n- $ i=1 $: $ r_{t_1} = r_0 = t_1 = 0 $\n- $ i=2 $: $ r_{t_2} = r_1 = t_2 = 1 $\n\nSo:  \n$ r_0 = 0 $  \n$ r_1 = 1 $  \n$ r_2 = ? $ — no constraint directly on $ r_2 $, but we can choose it.\n\nWe want to minimize distinct rooms.\n\nWe have $ r_0 = 0 $, $ r_1 = 1 $.  \nWe can set $ r_2 = 0 $ or $ r_2 = 1 $ — both are allowed (since no constraint forces $ r_2 $).\n\nSo possible assignments:  \n- $ r_0 = 0, r_1 = 1, r_2 = 0 $ → rooms: {0,1} → size 2  \n- $ r_0 = 0, r_1 = 1, r_2 = 1 $ → rooms: {0,1} → size 2  \n\nCannot use only one room: because $ r_0 = 0 $, $ r_1 = 1 $, so must have at least two distinct values.\n\nSo minimum is 2. ✅\n\n### Example 2: $ n=5 $, $ t = [0,1,2,1,2] $\n\nConstraints:\n- $ r_0 = 0 $\n- $ r_1 = 1 $\n- $ r_2 = 2 $\n- $ r_1 = 1 $ (again)\n- $ r_2 = 2 $ (again)\n\nSo forced: $ r_0 = 0 $, $ r_1 = 1 $, $ r_2 = 2 $\n\nNow $ r_3, r_4, r_5 $ are unconstrained.\n\nWe can assign them to existing values to minimize total distinct rooms.\n\nSo we have already 3 distinct rooms: 0,1,2.\n\nWe can set $ r_3 = 0 $, $ r_4 = 1 $, $ r_5 = 2 $ — total still 3.\n\nBut the sample says the sequence could be 1→2→3→1→2→1, which implies 3 rooms.\n\nWait, but the problem says: \"minimum possible number of rooms\" — and in the sample, answer is 3? But the problem says \"the sequence could be 1→2→3→1→2→1\" — that's 3 rooms.\n\nBut the problem says: \"In the only line print a single integer — the minimum possible number of rooms\"\n\nAnd in sample 2, the input is $ t = [0,1,2,1,2] $, and output should be 3.\n\nBut the problem says: \"In the second sample, the sequence could be 1→2→3→1→2→1\" — so 3 rooms.\n\nSo minimum is 3.\n\nBut why can't we use only 2 rooms?\n\nBecause we are forced:  \n$ r_0 = 0 $  \n$ r_1 = 1 $  \n$ r_2 = 2 $\n\nSo we must have at least three distinct room labels: 0, 1, 2.\n\nThus, the minimum number of rooms is the number of **distinct values in the set** $ \\{ t_1, t_2, \\dots, t_n \\} \\cup \\{0\\} $, because:\n\n- $ r_{t_i} = t_i $ for each $ i $, so for each distinct $ t_i $, we have a constraint that $ r_{t_i} = t_i $\n- Also, $ r_0 $ must equal $ t_i $ whenever $ t_i = 0 $, but since $ t_1 = 0 $ (because $ t_1 \\in \\{0\\} $), so $ r_0 = 0 $\n\nSo the set of forced room labels is $ S = \\{ t_1, t_2, \\dots, t_n \\} \\cup \\{0\\} $\n\nBut note: $ t_i \\geq 0 $, and $ t_i < i $, so 0 is always included (since $ t_1 = 0 $).\n\nSo $ S = \\{ t_1, t_2, \\dots, t_n \\} $ — because 0 is already in the list (as $ t_1 = 0 $).\n\nWait: is 0 always in $ \\{t_1, \\dots, t_n\\} $? Yes, because $ t_1 = 0 $.\n\nSo the set of forced room labels is exactly $ \\{ t_1, t_2, \\dots, t_n \\} $\n\nBut we are not forced to assign $ r_i = i $ for other $ i $ — only that $ r_{t_i} = t_i $\n\nSo the minimal number of distinct rooms is the number of **distinct values** in $ t_1, t_2, \\dots, t_n $\n\nBecause:\n\n- For each distinct value $ v $ that appears in $ t $, we must have $ r_v = v $ (since $ v = t_i $ for some $ i $, so $ r_{t_i} = t_i \\Rightarrow r_v = v $)\n- For any other minute $ j $ not equal to any $ t_i $, we can assign $ r_j $ to be one of the already-used values $ v \\in \\{t_1, \\dots, t_n\\} $\n- So total distinct rooms = number of distinct $ t_i $\n\nIn example 1: $ t = [0,1] $ → distinct values: {0,1} → size 2 ✅  \nIn example 2: $ t = [0,1,2,1,2] $ → distinct values: {0,1,2} → size 3 ✅\n\nThus, the answer is:  \n$$\n\\boxed{|\\{ t_1, t_2, \\dots, t_n \\}|}\n$$\n\nThat is, the number of **distinct values** in the given sequence $ t_1, \\dots, t_n $\n\n---\n\n### Final Formal Statement:\n\nLet $ n \\in \\mathbb{N} $, $ n \\geq 1 $, and let $ \\mathbf{t} = (t_1, t_2, \\dots, t_n) $ be a sequence of integers such that $ 0 \\leq t_i < i $ for all $ i \\in \\{1, \\dots, n\\} $.\n\nDefine the set $ S = \\{ t_1, t_2, \\dots, t_n \\} $.\n\nThen the minimum possible number of rooms is:\n\n$$\n|S|\n$$\n\nThat is, the number of distinct elements in $ \\mathbf{t} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF890C","tags":["greedy","implementation","trees"],"sample_group":[["2\n0 0","2"],["5\n0 1 0 1 3","3"]],"created_at":"2026-03-03 11:00:39"}}