AT_abc338_d [ABC338D] Island Tour

AtCoder 諸岛由 $N$ 个岛屿组成，这些岛屿通过 $N$ 座桥相互连接。每个岛屿编号为 $1$ 到 $N$，第 $i$ ($1 \leq i \leq N-1$) 座桥连接岛屿 $i$ 和岛屿 $i+1$，第 $N$ 座桥连接岛屿 $N$ 和岛屿 $1$，所有桥都是双向的。除了通过桥之外，没有其他方式可以在岛屿之间移动。 在 AtCoder 諸岛上，定期会举办从岛屿 $X_1$ 出发，依次访问岛屿 $X_2, X_3, \dots, X_M$ 的“旅行团”。在移动过程中，可以经过未被访问的其他岛屿，旅行团中经过桥的总次数被定义为旅行团的“长度”。 更严格地说，**旅行团**是满足以下所有条件的 $l+1$ 个岛屿的序列 $a_0, a_1, \dots, a_l$，其**长度**定义为 $l$： - 对于所有 $j$ ($0 \leq j \leq l-1$)，岛屿 $a_j$ 和 $a_{j+1}$ 之间有桥直接相连。 - 存在 $0 = y_1 < y_2 < \dots < y_M = l$，对于所有 $k$ ($1 \leq k \leq M$)，都有 $a_{y_k} = X_k$。 由于财政困难，AtCoder 諸岛决定封锁一座桥以减少维护费用。请你求出，合理选择要封锁的桥后，旅行团的最小长度是多少。

输入以如下格式从标准输入给出。 > $N$ $M$ $X_1$ $X_2$ $\dots$ $X_M$

请输出一个整数，表示封锁一座桥后旅行团的最小长度。

### 限制条件 - $3 \leq N \leq 2 \times 10^5$ - $2 \leq M \leq 2 \times 10^5$ - $1 \leq X_k \leq N$ - $X_k \neq X_{k+1}$ ($1 \leq k \leq M-1$) - 所有输入均为整数 ### 样例解释 1 - 封锁第 $1$ 座桥时：可以选择经过的岛屿序列为 $(a_0, a_1, a_2) = (1, 3, 2)$，依次访问岛屿 $1, 3, 2$，旅行团长度为 $2$，不存在更短的旅行团。 - 封锁第 $2$ 座桥时：可以选择经过的岛屿序列为 $(a_0, a_1, a_2, a_3) = (1, 3, 1, 2)$，依次访问岛屿 $1, 3, 2$，旅行团长度为 $3$，不存在更短的旅行团。 - 封锁第 $3$ 座桥时：可以选择经过的岛屿序列为 $(a_0, a_1, a_2, a_3) = (1, 2, 3, 2)$，依次访问岛屿 $1, 3, 2$，旅行团长度为 $3$，不存在更短的旅行团。 因此，合理选择要封锁的桥后，旅行团的最小长度为 $2$。 下图从左到右分别表示封锁第 $1, 2, 3$ 座桥的情况，带数字的圆圈表示岛屿，圆圈之间的线表示桥，蓝色箭头表示最短旅行团的路径。  ### 样例解释 2 在 $X_1, X_2, \dots, X_M$ 中，同一个岛屿可能会出现多次。 由 ChatGPT 4.1 翻译