Informatica Online Judge

  공항 게이트 할당 [2175 / 087F]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 17   Total Tried : 17


The Champion of this Problem (C++) : icp1481 - 0ms / 188byte
My Best Submission (C++) : N/A

[CCC2015S3]

Background

하루 동안 공항을 선물? 받았다!

공항에는 $1$번부터 $G$번까지 $G$개의 게이트(gate)들이 있다.

$P$대의 비행기들이 순서대로 공항에 도착해 착륙하는데, $i$번째로 도착한 비행기는 $1$, $2$, $3$, ... , $g_i$($1≤g_i≤G$) 중 하나의 게이트를 할당받아 사용할 수 있고, 그 비행기 보다 먼저 도착한 비행기가 먼저 사용하고 있는 게이트는 사용할 수 없다.

공항에 도착한 비행기가 사용할 수 있는 게이트가 없으면, 그 즉시 공항은 마비가 되고 다음 비행기들도 더 이상 착륙할 수 없게 된다.

공항을 선물?해 준 사람을 기쁘게 하기 위해서, 최대한 많은 비행기들에게 게이트를 할당해 착륙시켜야 한다. 최대로 착륙시킬 수 있는 비행기는 몇 대일까?

Input

첫 번째 줄에는 공항의 게이트 수 $G$가 입력된다.

두 번째 줄에는 순서대로 도착하는 비행기의 댓수 $P$가 입력된다.

그 다음부터 $P$개의 줄에는 $i$번째로 도착한 비행기가 사용할 수 있는 게이트의 최대 번호$g_i$가 순서대로 주어진다.

(사용할 수 있는 게이트의 최대 번호가 $g_i$이면, 그 비행기는 [$1$, $g_i$] 범위의 게이트들 중 하나를 할당받아 사용할 수 있다.)

[입력값의 정의역]
$1≤G≤10^5$
$1≤P≤10^5$
$1≤g_i≤G$

Output

최대로 착륙시킬 수 있는 비행기들의 댓수를 출력한다.

IO Example

입력 예시1
4
3
4
1
1

출력 예시1
2

*설명 : 1번째로 도착한 비행기는 아무 게이트나 할당해 착륙시킬 수 있지만, 1번 게이트를 사용하지 않도록 하는 것이 좋다. 2번째/3번째로 도착하는 비행기가 모두 1번 게이트까지만 사용할 수 있기 때문에 3대의 비행기를 모두 착륙시킬 수는 없다.


입력 예시2
4
6
2
2
3
3
4
4

출력 예시2
3

*설명 : 처음 2대의 비행기들은 1번/2번 게이트를 사용하도록 할당 한다. 3번째 비행기는 3번 게이트를 사용해야 한다. 5번째 비행기는 4번 게이트를 사용할 수 있지만. 4번째 비행기가 도착했을 때 사용할 수 있는 게이트가 없기 때문에 3대의 비행기가 착륙하고나면 공항이 마비된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]