分数: 300 分
问题陈述
高桥正在调查一条铁路线。这条线有 N 站,编号自 1 to N.
该生产线具有特殊的结构。从车站出发 i (1 \leq i \leq N-1),只有一列火车前往车站 P_i 已运行。在这里, P_i 是介于 1 和 N,包含在内,不同于 i。车站 N 为最终目的地,该站无列车出发 N.
高桥在车站出发 1 并反复登上每个车站唯一可用的火车,目标是到达车站 N。当他到达车站时旅程结束 N.
给出的输入使得从站开始 1 重复上述过程,他总会到达车站 N 在有限次数的移动中无需访问同一站两次。
查找从车站访问过的车站数量 1 直到到达车站 N。包括出发站(车站 1)和到达站(站 N)在计数中。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N (1 \leq i \leq N-1)
- P_i \neq i (1 \leq i \leq N-1)
- 保证站 从车站可到达 N 从车站可以到达 1 无需访问同一车站两次
- 所有输入值均为整数
输入
N
P_1 P_2 \cdots P_{N-1}
- 第一行包含一个整数 N,代表站数。
- 第二行包含 N-1 整数 P_1, P_2, \ldots, P_{N-1} 以空格分隔。 P_i 表示从车站乘火车可到达的下一站的编号 i。由于没有火车从车站出发 未给出 N, P_N 。
输出
一行打印从车站访问过的车站数量 1 直到到达车站 N (包括两个站 1 和车站 N).
示例输入 1
5 2 4 5 5
示例输出 1
4
示例输入 2
8 3 5 7 2 8 4 6
示例输出 2
8
示例输入 3
10 2 3 4 5 6 7 8 9 10
示例输出 3
10