일치

면접 대비

시간 제한2초메모리 제한512 MB

요약

N명의 참가자를 1번부터 N번 방에 배정할 때 여권 번호와 방 번호가 같은 참가자의 수를 최대로 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 정렬, 해시맵, 투 포인터
정답자: 아직 제출이 없습니다

문제

ICPC (Intergalactic Collegiate Programming Contest) 참가자들이 새로 지은 호텔에 묵게 되었다. 호텔에는 1부터 $N$ 까지 빠짐없이 번호가 붙은 1인실 $N$ 개가 있다. 각 참가자의 여권 번호는 1 이상 $10^9$ 이하의 정수로 주어진다. 서로 다른 행성에서 온 참가자의 여권 번호는 같을 수 있다.

배정을 기다리던 참가자 몇 명은 재미있는 상황이 가능하다는 것을 알아냈다. 여권 번호가 방 번호와 같아질 수 있다는 것이다. 그래서 참가자들은 이런 의문을 품었다. 일치하는 경우의 수를 최대로 만들도록 참가자를 배정한다면, 그 최대 개수는 얼마일까?

호텔의 방 개수와 참가자들의 여권 번호 목록이 주어질 때 이 질문의 답을 구하라.

입력

첫째 줄에 정수 $N$ 이 주어진다 ( $1 \le N \le 10^5$ ). 이어지는 $N$ 개 줄 중 $i$ 번째 줄에는 $i$ 번째 참가자의 여권 번호 $a\_i$ 가 주어진다 ( $1 \le a\_i \le 10^9$ ).

출력

참가자를 방에 배정할 때 얻을 수 있는 여권 번호와 방 번호의 일치 개수의 최댓값을 정수 하나로 출력한다.

예제2

예제 1
입력
```
5
1
3
5
7
5
```
예상 출력
```
3
```

예제 2

입력

예상 출력