P6399 [COI 2008] TAMNICA
题目描述
现在有一个无限大的迷宫，数字如图方式排列。两个数字之间的黑线表示有一堵墙隔开，如果没有则可以互相到达。
你从 $1$ 出发，出口在 $n$ 。现在由于地震，有一些墙倒了，这正好便利了你的通行。趁着人们的慌乱，你需要经过尽可能少的数字来迅速出逃。请你算出出逃最少需要的步数。
输入格式
输入第一行为一个整数 $n$ ，表示出口所在的格子。
第二行为一个整数 $k$，表示因地震倒塌的墙的数量。
接下来的 $k$ 行，每行一个整数 $b$，表示一堵倒塌的墙的一侧的数字。
另一侧的数字 $a$ 没有给出，但已知 $a
输出格式
输出一行一个整数，表示最少需要经过的数字的数量（不包含 $1$）。
说明/提示
#### 样例 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](https://hsin.hr/coci/archive/2007_2008/) [COI2008](https://hsin.hr/coci/archive/2007_2008/olympiad_tasks.pdf) *T3 TAMNICA***。