Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Gates

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 5.0 seconds

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 from 1 to g_i where (1 \le g_i \le 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 maximise the number of planes starting from the beginning that can all dock at different gates.

Input

The first line of input contains G \ (1 \le G \le 10^5), the number of gates at the airport.

The second line of input contains P \ (1 \le P ≤ 10^5), the number of planes which will land.

The next P lines contain one integer g_i \ (1 \le g_i \le G), such that the ith plane must dock at some gate from 1 to g_i, inclusive.

Output

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

Subtasks

  • (40%) Where P \le 2000 and G \le 2000.

Sample 1 Explaination

The first plane can go anywhere (since all slots are less than or equal 4), 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 2 Explaination

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.

  • Sample Input 1

    4
    3
    4
    1
    1
    

    Sample Output 1

    2
    
  • Sample Input 2

    4
    6
    2
    2
    3
    3
    4
    4
    

    Sample Output 2

    3