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$

输出格式

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

输入输出样例 #1

输入 #1

3 3
1 3 2

输出 #1

2

输入输出样例 #2

输入 #2

4 5
2 4 2 4 2

输出 #2

8

输入输出样例 #3

输入 #3

163054 10
62874 19143 77750 111403 29327 56303 6659 18896 64175 26369

输出 #3

390009

说明/提示

限制条件

• $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 翻译