环岛巡游

题目描述

AtCoder 群岛由 $N$ 座岛屿和连接它们的 $N$ 座桥构成。 岛屿编号为 $1$ 到 $N$，第 $i$ 座桥（$1 \le i \le 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 \le j \le l-1)$，岛屿 $a_j$ 和 $a_{j+1}$ 由一座桥直接相连。
• 存在某些 $0 = y_1 \lt y_2 \lt \dots \lt y_M = l$，使得对所有 $k\ (1 \le k \le M)$，都有 $a_{y_k} = X_k$。

由于财政困难，群岛将关闭一座桥以减少维护费用。 请问在最优化选择关闭哪座桥的情况下，巡游的最小可能长度是多少？

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$X_1$ $X_2$ $\dots$ $X_M$

输出格式

将答案作为整数输出。

样例

3 3
1 3 2

2

如果关闭第 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。

4 5
2 4 2 4 2

8

在 $X_1, X_2, \dots, X_M$ 中，同一座岛屿可能多次出现。

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

390009

数据范围

• $3 \le N \le 2 \times 10^5$
• $2 \le M \le 2 \times 10^5$
• $1 \le X_k \le N$
• $X_k \neq X_{k+1}\ (1 \le k \le M-1)$
• 所有输入值均为整数。