Island Tour

题目描述

AtCoder 群岛由 $N$ 个岛屿通过 $N$ 座桥连接。 岛屿编号为 $1$ 到 $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$。

由于财政困难，各岛将关闭一座桥以减少维护成本。 当关闭的桥被最优选择时，确定游览的最小可能长度。

输入格式

输入由标准输入给出，格式如下： $N$ $M$ $X_1$ $X_2$ $\dots$ $X_M$

输出格式

输出答案（整数）。

3 3
1 3 2

2

4 5
2 4 2 4 2

8

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

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 座桥：通过取岛屿序列 $(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$ 的情况。带数字的圆圈表示岛屿，连接圆圈的线表示桥，蓝色箭头表示最短游览路线。
相同的岛屿可能在 $X_1, X_2, \dots, X_M$ 中出现多次。

标签: AtCoder|abc338D

来源

AtCoder|abc338D