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 $.
Define $ 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).
Each 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} $.
We are to find the **minimum possible number of distinct rooms** $ |\{r_0, r_1, \dots, r_n\}| $ consistent with the constraints.
---
### Formal Mathematical Formulation:
**Given:**
- Integer $ n \geq 1 $
- Sequence $ \mathbf{t} = (t_1, t_2, \dots, t_n) $, where $ t_i \in \{0, 1, \dots, i-1\} $
**Define:**
- A sequence of room labels $ r_0, r_1, \dots, r_n $, where each $ r_i \in \mathbb{N} $ (room identifiers)
- Constraint: For each $ i \in \{1, 2, \dots, n\} $, $ r_i = r_{t_i} $
**Objective:**
Minimize $ \left| \{ r_0, r_1, \dots, r_n \} \right| $
---
### Key Insight:
The 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.
This 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 $).
The 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.
But 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 $.
However, 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**.
But 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.**
Therefore, 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 $.
Wait — 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 $.
Thus, **$ 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 $.
So 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.
Therefore, 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**.
But 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**.
Actually, 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} $.
We 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 $.
This 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**.
But 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.
Actually, 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.
But 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.
Thus, 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**.
But node 0 is always connected to all $ i $ such that $ t_i = 0 $, and recursively to others.
Actually, 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**?
No — consider: if $ t_1 = 0 $, $ t_2 = 0 $, $ t_3 = 1 $, then:
- $ r_1 = r_0 $
- $ r_2 = r_0 $
- $ r_3 = r_1 = r_0 $
So all equal.
But what if $ t_1 = 0 $, $ t_2 = 1 $, $ t_3 = 2 $? Then $ r_3 = r_2 = r_1 = r_0 $ — still one room.
Wait — then why is the first sample answer 2?
Sample 1: $ n = 2 $, $ t = [0, 1] $
So:
- $ r_1 = r_{t_1} = r_0 $
- $ r_2 = r_{t_2} = r_1 = r_0 $
So all rooms equal → only 1 room? But sample says answer is 2.
Contradiction?
Wait — let's re-read the problem:
> When he enters a room at minute #cf_span[i], he makes a note in his logbook with number #cf_span[ti]:
This means: at minute $ i $, he writes down the **room number he was in at minute $ t_i $**.
So the log entry at minute $ i $ is the **label of room $ r_{t_i} $**.
But the problem does **not** say that $ r_i = r_{t_i} $.
It says: at minute $ i $, he writes down the number of the room he was in at minute $ t_i $.
So the **log entry** $ t_i $ is the **value** of $ r_{t_i} $, not that $ r_i = r_{t_i} $.
Ah! Critical misinterpretation.
Let me re-analyze.
---
### Correct Interpretation:
- At minute $ i $, Petya is in room $ r_i $.
- 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} $.
- So the logbook contains the sequence $ r_{t_1}, r_{t_2}, \dots, r_{t_n} $.
- But we are **given** the sequence of written numbers: $ t_1, t_2, \dots, t_n $ — wait, no!
Wait, the problem says:
> The second line contains $ n $ non-negative integers $ t_1, t_2, \dots, t_n $ ($ 0 \leq t_i < i $) — notes in the logbook.
But it says: "he makes a note in his logbook with number $ t_i $".
So: **the number written at minute $ i $ is $ t_i $**.
But 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 $".
And: "he didn't write down number $ t_0 $".
So: **the value written at minute $ i $ is $ t_i $**.
But 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 $".
And: "he was in one of the rooms at minute 0".
So: the logbook entry at minute $ i $ is **the room number he was in at minute $ t_i $**.
But then, the value written is **the room label at time $ t_i $**, not the time index.
But the input gives us **$ t_i $** as the value written — so **$ t_i $ is the room number** he was in at minute $ t_i $.
Wait — that can’t be: the room numbers are arbitrary, and $ t_i $ is given as an integer between 0 and $ i-1 $.
Ah! Now I see the confusion.
The problem says:
> he makes a note in his logbook with number $ t_i $
and then says:
> The second line contains $ n $ non-negative integers $ t_1, t_2, \dots, t_n $ ($ 0 \leq t_i < i $) — notes in the logbook.
So: **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 $**.
So:
At minute $ i $, Petya writes down the **room number** he was in at minute $ t_i $.
But the value he writes is $ t_i $ (the integer given in input).
So:
$$
r_{t_i} = t_i
$$
Wait — that would mean: the room number at minute $ t_i $ is equal to the integer $ t_i $.
But room numbers are arbitrary — we can assign them.
So the constraint is:
For each $ i \in \{1, 2, \dots, n\} $, the room Petya was in at minute $ t_i $ has **label $ t_i $**.
That is:
$$
r_{t_i} = t_i
$$
And at minute $ i $, he is in some room $ r_i $, and he writes down $ r_{t_i} = t_i $.
So the **only constraints** are:
For each $ i \in \{1, \dots, n\} $, $ r_{t_i} = t_i $
Additionally, 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.
So the only hard constraints are:
- $ r_{t_i} = t_i $ for each $ i = 1, 2, \dots, n $
And 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 $.
Note: $ t_i < i $, so $ t_i \in \{0, 1, \dots, i-1\} $, so $ r_{t_i} $ is defined.
So we have a set of equations:
For each $ i \in \{1, \dots, n\} $: $ r_{t_i} = t_i $
We need to assign values to $ r_0, r_1, \dots, r_n $ satisfying these, and minimize $ |\{r_0, \dots, r_n\}| $
---
### Example 1: $ n=2 $, $ t = [0, 1] $
Constraints:
- $ i=1 $: $ r_{t_1} = r_0 = t_1 = 0 $
- $ i=2 $: $ r_{t_2} = r_1 = t_2 = 1 $
So:
$ r_0 = 0 $
$ r_1 = 1 $
$ r_2 = ? $ — no constraint directly on $ r_2 $, but we can choose it.
We want to minimize distinct rooms.
We have $ r_0 = 0 $, $ r_1 = 1 $.
We can set $ r_2 = 0 $ or $ r_2 = 1 $ — both are allowed (since no constraint forces $ r_2 $).
So possible assignments:
- $ r_0 = 0, r_1 = 1, r_2 = 0 $ → rooms: {0,1} → size 2
- $ r_0 = 0, r_1 = 1, r_2 = 1 $ → rooms: {0,1} → size 2
Cannot use only one room: because $ r_0 = 0 $, $ r_1 = 1 $, so must have at least two distinct values.
So minimum is 2. ✅
### Example 2: $ n=5 $, $ t = [0,1,2,1,2] $
Constraints:
- $ r_0 = 0 $
- $ r_1 = 1 $
- $ r_2 = 2 $
- $ r_1 = 1 $ (again)
- $ r_2 = 2 $ (again)
So forced: $ r_0 = 0 $, $ r_1 = 1 $, $ r_2 = 2 $
Now $ r_3, r_4, r_5 $ are unconstrained.
We can assign them to existing values to minimize total distinct rooms.
So we have already 3 distinct rooms: 0,1,2.
We can set $ r_3 = 0 $, $ r_4 = 1 $, $ r_5 = 2 $ — total still 3.
But the sample says the sequence could be 1→2→3→1→2→1, which implies 3 rooms.
Wait, 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.
But the problem says: "In the only line print a single integer — the minimum possible number of rooms"
And in sample 2, the input is $ t = [0,1,2,1,2] $, and output should be 3.
But the problem says: "In the second sample, the sequence could be 1→2→3→1→2→1" — so 3 rooms.
So minimum is 3.
But why can't we use only 2 rooms?
Because we are forced:
$ r_0 = 0 $
$ r_1 = 1 $
$ r_2 = 2 $
So we must have at least three distinct room labels: 0, 1, 2.
Thus, the minimum number of rooms is the number of **distinct values in the set** $ \{ t_1, t_2, \dots, t_n \} \cup \{0\} $, because:
- $ r_{t_i} = t_i $ for each $ i $, so for each distinct $ t_i $, we have a constraint that $ r_{t_i} = t_i $
- 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 $
So the set of forced room labels is $ S = \{ t_1, t_2, \dots, t_n \} \cup \{0\} $
But note: $ t_i \geq 0 $, and $ t_i < i $, so 0 is always included (since $ t_1 = 0 $).
So $ S = \{ t_1, t_2, \dots, t_n \} $ — because 0 is already in the list (as $ t_1 = 0 $).
Wait: is 0 always in $ \{t_1, \dots, t_n\} $? Yes, because $ t_1 = 0 $.
So the set of forced room labels is exactly $ \{ t_1, t_2, \dots, t_n \} $
But we are not forced to assign $ r_i = i $ for other $ i $ — only that $ r_{t_i} = t_i $
So the minimal number of distinct rooms is the number of **distinct values** in $ t_1, t_2, \dots, t_n $
Because:
- 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 $)
- 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\} $
- So total distinct rooms = number of distinct $ t_i $
In example 1: $ t = [0,1] $ → distinct values: {0,1} → size 2 ✅
In example 2: $ t = [0,1,2,1,2] $ → distinct values: {0,1,2} → size 3 ✅
Thus, the answer is:
$$
\boxed{|\{ t_1, t_2, \dots, t_n \}|}
$$
That is, the number of **distinct values** in the given sequence $ t_1, \dots, t_n $
---
### Final Formal Statement:
Let $ 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\} $.
Define the set $ S = \{ t_1, t_2, \dots, t_n \} $.
Then the minimum possible number of rooms is:
$$
|S|
$$
That is, the number of distinct elements in $ \mathbf{t} $.