Matches

Interview

Time limit2sMemory limit512 MB

Summary

Assign N participants to rooms 1..N so that the number of participants whose passport number equals their room number is maximized.

Level: Medium5 of 10
Topics: Greedy, Sorting, Hash map, Two pointers
Solved: No attempts yet

Problem

The participants of the ICPC (Intergalactic Collegiate Programming Contest) have been lodged in a newly built hotel. The hotel has $N$ single rooms, numbered with the integers from 1 to $N$ with no gaps. Each participant has a known passport number, an integer from 1 to $10^9$ inclusive. Participants from different planets may have the same passport number.

While waiting to be checked in, several participants noticed that a funny situation is possible: a passport number may coincide with a room number. They then asked themselves the following question. What is the largest number of such coincidences that would be possible if the participants were deliberately assigned to rooms so as to maximize that number?

Given the number of rooms in the hotel and the list of participants' passport numbers, find the answer to this question.

Input

The first line of the input contains a single integer $N$ ( $1 \le N \le 10^5$ ). The $i$ -th of the following $N$ lines contains an integer $a\_i$ , the passport number of the $i$ -th participant ( $1 \le a\_i \le 10^9$ ).

Output

Print a single integer: the largest number of coincidences between passport numbers and room numbers that can be obtained when the participants are assigned to rooms.

Examples2

Example 1
Input
```
5
1
3
5
7
5
```
Expected output
```
3
```

Example 2

Input

Expected output