G. Piano Concerto
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sergei Rachmaninoff is hosting a competition — which if his students can best play his latest composition - Opus 18 Piano Concerto No. 2. He has $$$n$$$ students, numbered $$$1, 2, ... n$$$, each of which is also part of various circles in the Russian mafia. The students all have a rival who they want to target — student $$$i$$$ wants to shoot down student $$$s_i$$$. Note that it is possible for $$$i = s_i$$$ (the nerves ... ).

You, Rachmaninoff's assistant, want to minimize the bloodshed. Therefore, you want to order the students in such a way so as to minimize the bloodshed — you don't like violence. The students play sequentially, and if its a student's turn but they are already dead, the competition moves on to the next in line. Each students best opportunity to shoot their assigned rival is as they are exiting the stage, therefore, student $$$i$$$ only attempts to shoot $$$s_i$$$ once they have finished performing, before the next performance starts. Find the minimum number of casualties across all possible permutations of students at this event.

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 200,000$$$) — the number of students.

The second line contains $$$n$$$ space separated integers $$$s_1, s_2, ... s_n$$$ ($$$1 \le s_i \le n$$$) — the student who the $$$i$$$th student wants to shoot down, respectively.

Output

A single integer that gives the minimum number of casualties in the competition across all permutations of students.

Examples
Input
8
2 3 2 2 6 7 8 5
Output
3
Input
5
1 2 3 4 5
Output
5
Input
6
2 3 4 5 6 1
Output
3
Input
5
2 3 1 2 4
Output
3
Note

In the first sample, we can achieve 3 deaths (and no better) from the order of performances - 1 2 3 4 5 6 7 8.

In the second sample, everyone is able to target themself, so .

The third sample is a cycle - the order 1 2 3 4 5 6 ensures only 3 deaths.

In the fourth sample, the order 5 1 2 3 4 targets 3 people, with students 3 and 5 surviving at the end.