P9812 [CCC 2015 S3] Gates

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.

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 one integer on a single line, representing the maximum number of planes that can be assigned.

**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