공항

면접 대비

시간 제한1초메모리 제한256 MB

요약

도착 순서대로 각 비행기는 gi 이하 빈 게이트 중 가장 큰 번호에 도킹하고 빈 게이트가 없으면 공항을 닫습니다.

난이도: 보통10점 중 4점
유형: 유니온 파인드, 그리디
정답자: 아직 제출이 없습니다

문제

공항에는 게이트가 $G$ 개 있고, 각 게이트에는 $1$ 번부터 $G$ 번까지 번호가 붙어 있다.

비행기 $P$ 대가 정해진 순서대로 도착한다. $i$ 번째 비행기는 $1$ 번부터 $g_i$ 번 게이트 중에서 아직 비어 있는 게이트 하나에 영구적으로 도킹한다. 한 게이트에는 비행기 한 대만 도킹하고, 이미 도킹한 비행기는 다른 게이트로 옮기지 못한다. 도착한 비행기가 쓸 수 있는 게이트가 하나도 남지 않으면 공항이 폐쇄되고, 그 뒤로는 어떤 비행기도 도착하지 못한다.

도킹시키는 비행기 수를 최대로 하고 싶다. 최대 몇 대를 도킹시킬 수 있는가?

입력

첫째 줄에 게이트의 수 $G$ ( $1 \le G \le 10^5$ )가 주어진다.

둘째 줄에 비행기의 수 $P$ ( $1 \le P \le 10^5$ )가 주어진다.

이어지는 $P$ 개의 줄에 $i$ 번째 비행기가 쓸 수 있는 게이트 번호의 상한 $g_i$ ( $1 \le g_i \le G$ )가 도착 순서대로 한 줄에 하나씩 주어진다.

출력

도킹시킬 수 있는 비행기의 최대 개수를 한 줄에 출력한다.

예제2

예제 1
입력
```
4
3
4
1
1
```
예상 출력
```
2
```
예제 2
입력
```
4
6
2
2
3
3
4
4
```
예상 출력
```
3
```