Choose but not both

★★★★★

2.8

13 votes

Algorithms, Depth First Search, Dynamic Programming, Graphs, Trees

Details

Submissions

Discussion

Editorial

Problem

The alone Y has another array $a_1, a_2, ..., a_n$ that $1 \leq a_i \leq n$ . this time Y wants to choose some numbers from $1$ to $n$ that there is no $i$ that both $i$ and $a_i$ is chosen.

What is the maximum amount of numbers that Y can choose?

Input

First line contains only $n$ , legnth of array.

Second line contains the array elements $a_1, a_2, ..., a_n$ separated by space.

$1 \leq n \leq 3 \times 10^5$

$1 \leq a_i \leq n$

Output

The only line of output contains an integer, maximum amount of numbers that Y can choose.

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Y cannot choose $3$ because $a_3 = 3$ .

Y cannot choose both $1$ and $2$ because $a_2 = 1$ so Y can choose only one number (either $1$ or $2$ ).