分数: 425 点
问题陈述
AtCoder 群岛包括 N 岛屿由以下连接 N 桥梁。 岛屿编号为 1 to N,以及 i第桥(1\leq i\leq N-1) 连接岛屿 i 和 i+1 双向,而 N第一座桥连接岛屿 N 和 1 双向。 除了过桥之外,没有其他办法可以在岛屿之间旅行。
在岛屿上, 游览 从岛屿出发的 从岛屿开始 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.
由于财政困难,岛屿将关闭一座桥梁以减少维护成本。 确定最佳选择要关闭的桥梁时可能的最短游览长度。
约束
- 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 X_2 \dots X_M
输出
将答案打印为整数。
示例输入 1
3 3 1 3 2
示例输出 1
2
- 如果第一座桥关闭:按岛屿顺序 (a_0, a_1, a_2) = (1, 3, 2), 可以游览岛屿 1, 3, 2 按顺序,以及长度的游览 2 可以进行。没有更短的旅行。
- 如果第二座桥关闭:通过采取岛屿序列 (a_0, a_1, a_2, a_3) = (1, 3, 1, 2), 可以游览岛屿 1, 3, 2 按顺序,以及长度的游览 3 可以进行。没有更短的旅行。
- 如果第三座桥关闭:按岛屿顺序 (a_0, a_1, a_2, a_3) = (1, 2, 3, 2), 可以游览岛屿 1, 3, 2 按顺序,以及长度的游览 3 可以进行。没有更短的旅行。
因此,最优选择关闭桥梁时可能的最小游览长度为 2.
下图从左到右依次为桥接时的情况 1, 2, 3 分别关闭。带数字的圆圈代表岛屿,连接圆圈的线代表桥梁,蓝色箭头代表最短路线。

示例输入 2
4 5 2 4 2 4 2
示例输出 2
8
同一岛屿可能会多次出现 X_1, X_2, \dots, X_M.
示例输入 3
163054 10 62874 19143 77750 111403 29327 56303 6659 18896 64175 26369
示例输出 3
390009