문제1447--공항 도킹 시스템

1447: 공항 도킹 시스템

[만든사람 : ]
시간제한 : 1.000 sec  메모리제한 : 128 MB  제출 : 14  맞은 사람 : 3

제출  

문제 설명

씨큐브국제공항이 있다. 이 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 
공항에는 P개의 비행기가 순서대로 도착할 예정이며, 민철이는 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도킹할 수 없다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다. 공항이 폐쇄되기 전까지 가장 많은 비행기를 공항에 도킹시키고 싶다.  여러분은 민철이를 도울 수 있는 씨큐브국제공항에 비행기를 최대 몇 대 도킹시킬 수 있는지 확인할 수 있는 프로그램을 작성하시오.

입력 설명

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력 설명

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

입력 예시1 Copy

4
3
4
1
1

출력 예시1 Copy

2

입력 예시2 Copy

4
6
2
2
3
3
4
4

출력 예시2 Copy

3

도움

예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다.
예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불가능하다.

출처/분류