Airport

Interview

Time limit1sMemory limit256 MB

Summary

Each arriving plane takes the largest free gate up to its limit gi, and the count stops at the first plane with no free gate.

Level: Medium4 of 10
Topics: Union-find, Greedy
Solved: No attempts yet

Problem

An airport has $G$ gates, numbered $1$ through $G$ .

$P$ planes arrive in a fixed order. Plane $i$ docks permanently at one gate that is still empty among gates $1$ through $g_i$ . A gate holds at most one plane, and a plane that has docked never moves to another gate. If no gate is left for the plane that is arriving, the airport closes and no further plane arrives.

Dock as many planes as possible. How many planes dock at most?

Input

The first line contains the number of gates $G$ ( $1 \le G \le 10^5$ ).

The second line contains the number of planes $P$ ( $1 \le P \le 10^5$ ).

Each of the next $P$ lines contains one integer $g_i$ ( $1 \le g_i \le G$ ), the highest gate number that plane $i$ can use, given in arrival order.

Output

Print the maximum number of planes that can dock, on one line.

Examples2

Example 1
Input
```
4
3
4
1
1
```
Expected output
```
2
```
Example 2
Input
```
4
6
2
2
3
3
4
4
```
Expected output
```
3
```