CF433C Ryouko's Memory Note

绫子是个极其健忘的女孩，甚至会忘记刚刚发生的事情。为了帮助记忆，她随身携带了一本笔记本，被称为“绫子的记忆笔记”。她会把所见所闻都记在笔记本上，这本笔记本也变成了她的记忆。 尽管绫子很健忘，但天生拥有极佳的分析能力。然而，分析很大程度上依赖于收集到的信息，也就是记忆。因此，每当她需要分析时，就得在笔记本中翻查信息，这是一项苦差事。 绫子的笔记本共有 $n$ 页，页码从 $1$ 到 $n$。为简化实际操作（也便于解这道题），我们假定，从第 $x$ 页翻到第 $y$ 页，需要翻动 $|x-y|$ 页。在分析过程中，绫子需要查找 $m$ 条信息，第 $i$ 条信息记录在第 $a_{i}$ 页。信息必须按照一定顺序依次查阅，因此绫子需要翻动的总页数为 $\sum\limits_{i=2}^{m} |a_{i}-a_{i-1}|$ 。 为了减少需要翻动的页数，绫子可以选择将笔记本中的两页合并。具体来说，如果绫子将第 $x$ 页合并到第 $y$ 页（$1\leq x,y\leq n$），她会把第 $x$ 页上的所有信息转移到第 $y$ 页，同时把序列 $a$ 中所有等于 $x$ 的元素替换为 $y$。注意，$x$ 与 $y$ 可以相同，这种情况下不会发生任何变化。 请你求出，绫子在查找信息前至多可以进行一次上述合并操作，使得她需要翻动的总页数最少。注意答案可能超过 $32$ 位整数范围。

输入的第一行为两个整数 $n$ 和 $m$（$1\leq n,m\leq 10^5$）。 接下来一行包含 $m$ 个用空格分隔的整数：$a_1,a_2,\ldots,a_m$（$1\leq a_i\leq n$）。

输出一个整数，即绫子最少需要翻动的页数。

在第一个样例中，最优的做法是将第 4 页合并到第 3 页，合并后序列 $a$ 变成 $\{1,2,3,3,3,2\}$，此时需要翻动的页数为 $|1-2|+|2-3|+|3-3|+|3-3|+|3-2|=3$。 在第二个样例中，最优的做法是将第 9 页合并到第 4 页。 由 ChatGPT 5 翻译