A - People Who Don't Receive Presents Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君のクラスでは、クリスマス会でプレゼント渡しを行います。クラスには N 人の生徒がおり、それぞれ 1 から N までの出席番号が付けられています。

プレゼント渡しのルールは次の通りです。各生徒はちょうど 1 つのプレゼントを用意し、自分以外のクラスメイト 1 人を選んで渡します。このとき、複数の生徒が同じ相手を選ぶこともあります。

プレゼント渡しが終わった後、高橋君はプレゼントを 1 つも受け取れなかった生徒がいることに気づきました。

各生徒 i （ 1 \leq i \leq N ）がプレゼントを渡す相手の出席番号 T_i が与えられます。プレゼントを 1 つも受け取れなかった生徒の人数を求めてください。

制約

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq N
  • T_i \neq i （各生徒は自分自身にはプレゼントを渡さない）
  • 入力はすべて整数である

入力

N
T_1 T_2 \ldots T_N
  • 1 行目には、クラスの生徒数を表す整数 N が与えられる。
  • 2 行目には、生徒 i （ 1 \leq i \leq N ）がプレゼントを渡す相手の出席番号 T_i が、スペース区切りで N 個与えられる。

出力

プレゼントを 1 つも受け取れなかった生徒の人数を 1 行で出力せよ。

入力例 1

5
2 1 1 2 3

出力例 1

2

入力例 2

8
2 3 4 5 6 7 8 1

出力例 2

0

入力例 3

10
3 1 1 1 3 7 8 7 10 9

出力例 3

4

Score : 266 pts

Problem Statement

Takahashi's class is holding a present exchange at their Christmas party. There are N students in the class, each assigned a student number from 1 to N.

The rules for the present exchange are as follows. Each student prepares exactly 1 present and chooses one classmate other than themselves to give it to. Multiple students may choose the same recipient.

After the present exchange, Takahashi noticed that some students didn't receive any presents at all.

Given the student number T_i of the recipient that each student i (1 \leq i \leq N) gives their present to, find the number of students who didn't receive any presents.

Constraints

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq T_i \leq N
  • T_i \neq i (no student gives a present to themselves)
  • All input values are integers

Input

N
T_1 T_2 \ldots T_N
  • The first line contains an integer N, representing the number of students in the class.
  • The second line contains N space-separated integers, where T_i is the student number of the recipient that student i (1 \leq i \leq N) gives their present to.

Output

Print the number of students who didn't receive any presents, on a single line.

Sample Input 1

5
2 1 1 2 3

Sample Output 1

2

Sample Input 2

8
2 3 4 5 6 7 8 1

Sample Output 2

0

Sample Input 3

10
3 1 1 1 3 7 8 7 10 9

Sample Output 3

4