Description

There is an infinite maze where the numbers are arranged as shown in the figure. A black line between two numbers means there is a wall separating them; if there is no line, then you can move between them.

You start from $1$, and the exit is at $n$. Now, because of an earthquake, some walls have collapsed, which makes it easier for you to move around. Taking advantage of the chaos, you need to escape as fast as possible by passing through as few numbers as you can. Please compute the minimum number of steps needed to escape.

Input Format

The first line contains an integer $n$, which indicates the cell where the exit is located.

The second line contains an integer $k$, which indicates the number of walls that collapsed due to the earthquake.

The next $k$ lines each contain an integer $b$, meaning the number on one side of a collapsed wall.

The number $a$ on the other side is not given, but it is known that $a<b$, so you can derive the value of $a$ yourself and thus determine which wall collapsed. Of course, some numbers (such as $2,3,5,7,10,13$) will never be a value of $b$.

Output Format

Output one integer in one line, indicating the minimum number of numbers that need to be passed through (not including $1$).

31
9
15
25
30
6
9
19
24
27
4

6

10000
5
52
4
9
25
27

9953

Hint

Explanation for Sample 1

The state of the maze after the earthquake for Sample $1$ is shown in the figure.

The route $1-4-15-14-13-30-31$ escapes the fastest. A total of $6$ numbers are passed through.

Constraints

• For $50\%$ of the testdata, $n\le 10^6$.
• For $100\%$ of the testdata, $1\le n\le 10^{15}$, $1\le k\le 10^5$, $4\le b\le 10^{15}$.

Note

Translated from COCI2007-2008 COI2008 T3 TAMNICA。

Translated by ChatGPT 5