B - メッセージの転送 解説 /

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

配点 : 300 点

問題文

高橋君は N 人のメンバーからなるグループでメッセージの転送実験を行っています。

メンバーには 1 から N までの番号が付けられており、メンバー i (1 \leq i \leq N) にはあらかじめ転送先のメンバー番号 P_i がちょうど 1 つ設定されています（ただし P_i \neq i）。

高橋君はメンバー 1 にメッセージを渡します。メッセージは常にちょうど 1 人のメンバーだけが持っており、最初はメンバー 1 が持っています。メッセージを受け取ったメンバーは 受け取り済み として記録されます。メンバー 1 は最初にメッセージを受け取ったものとして、受け取り済みとなります。

その後、転送は次のルールに従って繰り返し行われます：

  1. 現在メッセージを持っているメンバーを i とする。
  2. メンバー i の転送先であるメンバー P_i が受け取り済みであるかを確認する。
  • メンバー P_i が まだ受け取り済みでない 場合、メンバー i はメッセージをメンバー P_i へ転送する。これにより、メンバー i はメッセージを持たなくなり、メンバー P_i がメッセージを持つようになる。メンバー P_i は受け取り済みとして記録される。その後、ステップ 1 に戻る。
  • メンバー P_i が すでに受け取り済みである 場合、転送は行われず、メンバー i がメッセージを持ったまま実験は終了する。

実験が終了するまでに受け取り済みとなったメンバーの人数（メンバー 1 を含む）を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • P_i \neq i (1 \leq i \leq N)
  • 入力はすべて整数

入力

N
P_1 P_2 \ldots P_N
  • 1 行目には、メンバーの人数を表す整数 N が与えられる。
  • 2 行目には、メンバー 1, 2, \ldots, N のそれぞれの転送先の番号を表す整数 P_1, P_2, \ldots, P_N が、この順にスペース区切りで与えられる。

出力

実験が終了するまでに受け取り済みとなったメンバーの人数を 1 行で出力してください。

入力例 1

4
2 3 4 1

出力例 1

4

入力例 2

6
3 1 2 5 6 4

出力例 2

3

入力例 3

10
2 3 1 5 6 7 8 9 10 4

出力例 3

3

Score : 300 pts

Problem Statement

Takahashi is conducting a message forwarding experiment with a group of N members.

The members are numbered from 1 to N, and each member i (1 \leq i \leq N) has exactly one predetermined forwarding destination member number P_i (where P_i \neq i).

Takahashi gives a message to member 1. The message is always held by exactly one member, and initially member 1 holds it. A member who receives the message is recorded as received. Member 1 is considered to have received the message at the start, and is thus marked as received.

After that, forwarding is repeated according to the following rules:

  1. Let i be the member currently holding the message.
  2. Check whether member P_i, the forwarding destination of member i, has already received the message.
  • If member P_i has not yet received the message, member i forwards the message to member P_i. As a result, member i no longer holds the message, and member P_i now holds the message. Member P_i is recorded as received. Then, return to step 1.
  • If member P_i has already received the message, no forwarding takes place, and the experiment ends with member i still holding the message.

Determine the number of members who have been recorded as received by the time the experiment ends (including member 1).

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N
  • P_i \neq i (1 \leq i \leq N)
  • All inputs are integers

Input

N
P_1 P_2 \ldots P_N
  • The first line contains an integer N, representing the number of members.
  • The second line contains integers P_1, P_2, \ldots, P_N, representing the forwarding destination numbers of members 1, 2, \ldots, N respectively, separated by spaces in this order.

Output

Print in one line the number of members who have been recorded as received by the time the experiment ends.

Sample Input 1

4
2 3 4 1

Sample Output 1

4

Sample Input 2

6
3 1 2 5 6 4

Sample Output 2

3

Sample Input 3

10
2 3 1 5 6 7 8 9 10 4

Sample Output 3

3