2015 Canadian Computing Competition, Stage 1

Problem S3: Gates

For your birthday, you were given an airport.

The airport has G gates, numbered from 1 to G.

P planes arrive at the airport, one after another. You are to assign the i-th plane to permanently dock at any gate 1, …, g_i (1 ≤ g_i ≤ G), at which no previous plane has docked. As soon as a plane cannot dock at any gate, the airport is shut down and no future planes are allowed to arrive.

In order to keep the person who gave you the airport happy, you would like to maximize the number of planes starting from the beginning that can all dock at different gates.

Input

The first line of input contains G (1 ≤ G ≤ 10⁵), the number of gates at the airport.
The second line of input contains P (1 ≤ P ≤ 10⁵), the number of planes which will land.
The next P lines contain one integer g_i (1 ≤ g_i ≤ G), such that the ith plane must dock at some gate from 1 to g_i, inclusive.

Note that for at least 40% of the marks for this question, P ≤ 2000 and G ≤ 2000.

Output

Output the maximum number of planes that can land starting from the beginning.

Sample Input 1

4
3
4
1
1

Sample Output 1

2

Explanation of Sample 1

The first plane can go anywhere, but it is best to not put it into Gate 1. Notice that planes 2 and 3 both want to dock into Gate 1, so plane 3 is unable to dock.

Sample Input 2

4
6
2
2
3
3
4
4

Sample Output 2

3

Explanation of Sample 2

The first two planes will dock in gates 1 and 2 (in any order). The third plane must dock at Gate 3. Thus, the fourth plane cannot dock anywhere, and the airport is closed, even though plane 5 would have been able to dock.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 256M
Added: Feb 21, 2015
Author: SourSpinach

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

A new batch with stronger test cases has been added. The popular O(N[sup]2[/sup]) solution now fails (as it should).

what does "stronger test cases" mean?

When you submit a program, the judge gives input to your program (input data) and compares it to the right answer (output data) to check if it's right. A single test case is made of one set of input data and one set of output data.
A test case is stronger if it is more difficult to solve.

why would any plane need to dock at a specific dock? 

You need to maximize the total number of planes docked.