Problem Description

On a coastline, there are $n$ lighthouses in a row, numbered from $1$ to $n$ from left to right. You need to light up some of them to guide ships. You are given a lighting sequence $a_1, a_2, \dots, a_m$, where the $i$-th operation means trying to light the lighthouse numbered $a_i$. However, to save energy, if lighthouse $a_i - 1$ or lighthouse $a_i + 1$ has already been lit, then lighthouse $a_i$ cannot be lit and this operation will be skipped. Of course, the same lighthouse will be lit at most once.

You may choose a subsequence from the given lighting sequence (keeping the relative order of operations), and execute the lighting operations one by one in the order of the subsequence. What is the maximum number of lighthouses that can be successfully lit?

Input Format

The first line contains two positive integers $n, m$, separated by a space.

The second line contains $m$ positive integers $a_1, a_2, \dots, a_m$, with a space between adjacent integers.

Output Format

Output one line containing one integer, which is the answer.

10 9
1 3 2 5 2 10 9 6 5

4

Hint

Sample Explanation

One possible plan: keep the subsequence $1, 3, 5, 9$, which can light up $4$ lighthouses.

Testdata Scale and Constraints

For $40\%$ of the test cases, $1 \le n, m \le 5000$.

For all test cases, $1 \le n, m \le 10^6$, and $1 \le a_i \le n$.

Translated by ChatGPT 5