Problem Description

An airport has $n$ gates. You need to assign $m$ planes in order. The $i$-th plane can only use gates $1 \sim g_{i}$. Each gate can be used by at most one plane permanently. When there is no gate available for some plane, the airport will close, and the planes after that cannot dock.

Please determine a plan that maximizes the number of planes that can be assigned a gate.

Input Format

The first line contains an integer $n$.

The second line contains an integer $m$.

The next $m$ lines each contain an integer $g_{i}$.

Output Format

Output one integer on a single line, representing the maximum number of planes that can be assigned.

4
3
4
1
1

2

4
6
2
2
3
3
4
4

3

Hint

Constraints:

For $40\%$ of the testdata, $1 \leq n,m \leq 2 \times 10^{3}$.

For $100\%$ of the testdata, $1 \leq n,m \leq 10^{5}$, and $1 \leq g_{i} \leq n$.

In this problem, Subtask 0 uses the original problem testdata, and Subtask 1 uses Hack testdata. Hack testdata is not scored.

Translated by ChatGPT 5