B - 駅から駅へ 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋君は、鉄道路線の調査をしています。この路線には N 個の駅があり、それぞれ 1 から N までの番号が付けられています。

この路線は特殊な構造をしています。駅 i（1 \leq i \leq N-1）からは、駅 P_i へ向かう列車だけが運行されています。ここで P_i は i とは異なる 1 以上 N 以下の整数です。駅 N は最終目的地であり、駅 N から出発する列車はありません。

高橋君は駅 1 から出発し、各駅で運行されている唯一の列車に乗ることを繰り返して駅 N を目指します。駅 N に到着した時点で移動は終了します。

入力は、駅 1 から上記の移動を繰り返すと、同じ駅を2度訪れることなく有限回の移動で必ず駅 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)
  • 駅 1 から駅 N に、同じ駅を2度訪れることなく到達可能であることが保証される
  • 入力はすべて整数

入力

N
P_1 P_2 \cdots P_{N-1}
  • 1 行目には、駅の数を表す整数 N が与えられる。
  • 2 行目には、N-1 個の整数 P_1, P_2, \ldots, P_{N-1} がスペース区切りで与えられる。P_i は駅 i から列車で向かう次の駅の番号を表す。駅 N から出発する列車はないため、P_N は与えられない。

出力

駅 1 から駅 N に到達するまでに訪れる駅の個数（駅 1 と駅 N を含む）を 1 行で出力せよ。

入力例 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

Score : 300 pts

Problem Statement

Takahashi is investigating a railway line. This line has N stations, numbered from 1 to N.

This line has a special structure. From station i (1 \leq i \leq N-1), only a train heading to station P_i is operated. Here, P_i is an integer between 1 and N, inclusive, that is different from i. Station N is the final destination, and no trains depart from station N.

Takahashi starts at station 1 and repeatedly boards the only train available at each station, aiming to reach station N. The journey ends when he arrives at station N.

The input is given such that starting from station 1 and repeating the above process, he will always reach station N in a finite number of moves without visiting the same station twice.

Find the number of stations visited from station 1 until reaching station N. Include both the departure station (station 1) and the arrival station (station N) in the count.

Constraints

  • 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)
  • It is guaranteed that station N can be reached from station 1 without visiting the same station twice
  • All input values are integers

Input

N
P_1 P_2 \cdots P_{N-1}
  • The first line contains an integer N, representing the number of stations.
  • The second line contains N-1 integers P_1, P_2, \ldots, P_{N-1} separated by spaces. P_i represents the number of the next station reachable by train from station i. Since no trains depart from station N, P_N is not given.

Output

Print in one line the number of stations visited from station 1 until reaching station N (including both station 1 and station N).

Sample Input 1

5
2 4 5 5

Sample Output 1

4

Sample Input 2

8
3 5 7 2 8 4 6

Sample Output 2

8

Sample Input 3

10
2 3 4 5 6 7 8 9 10

Sample Output 3

10