← 返回题目列表

AtCoder · abc338_d

G. 海岛游

中文机器翻译题面 查看原题

分数: 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