题目描述

现在有一个无限大的迷宫，数字如图方式排列。两个数字之间的黑线表示有一堵墙隔开，如果没有则可以互相到达。

你从 $1$ 出发，出口在 $n$ 。现在由于地震，有一些墙倒了，这正好便利了你的通行。趁着人们的慌乱，你需要经过尽可能少的数字来迅速出逃。请你算出出逃最少需要的步数。

输入格式

输入第一行为一个整数 $n$ ，表示出口所在的格子。

第二行为一个整数 $k$，表示因地震倒塌的墙的数量。

接下来的 $k$ 行，每行一个整数 $b$，表示一堵倒塌的墙的一侧的数字。

另一侧的数字 $a$ 没有给出，但已知 $a<b$，所以你可以自己推导出 $a$ 的值，进而得出是哪堵墙倒塌了。当然，有些数字（比如 $2,3,5,7,10,13$） 永远不会是 $b$ 数字。

输出格式

输出一行一个整数，表示最少需要经过的数字的数量（不包含 $1$）。

31
9
15
25
30
6
9
19
24
27
4

6

10000
5
52
4
9
25
27

9953

提示

样例 1 解释

对于样例 $1$ 的地震后迷宫的状态如图所示。

$1-4-15-14-13-30-31$ 这条线路溜得最快。共经过了 $6$ 个数字。

数据规模与约定

• 对于 $50\%$ 的数据，$n\le 10^6$；
• 对于 $100\%$ 的数据，$1\le n\le 10^{15}$，$1\le k\le 10^5$，$4\le b\le 10^{15}$。

说明

题目译自 COCI2007-2008 COI2008 T3 TAMNICA。