凉子是一个极其健忘的女孩,她甚至会忘记刚刚发生的事情。所以为了记住,她随身带着一本笔记本,叫做凉子的记忆笔记。她把看到的、听到的写在笔记本上,笔记本就成了她的记忆。
凉子虽然健忘,但她也天生具有高超的分析能力。然而,分析很大程度上依赖于收集的信息,换句话说,依赖于记忆。因此,每当她需要分析时,她都必须翻阅笔记本,这是一项艰巨的工作。
Ryouko 的笔记本由 n 页组成,编号从 1 到 n。为了让生活(以及这个问题)更容易,我们认为从第 x 页翻到第 y 页,|x - y|应该翻页。在分析过程中,Ryouko需要m条信息,第i条信息在ai页面上。信息必须按顺序从笔记本中读取,因此 Ryouko 需要翻的总页数为 $$\sum_{i=1}^{m-1} |a_{i+1} - a_i|$$。
Ryouko 希望减少需要翻页的数量。为了实现这一目标,她可以合并笔记本的两页。如果 Ryouko 将页面 x 合并到页面 y,她会将页面 x 上的所有信息复制到 y(1 ≤ x,y ≤ n),因此,序列 a 中属于 x 的所有元素都将变成 y。请注意,x 可以等于 y,在这种情况下不会发生任何变化。
请告诉 Ryouko 她需要翻的最少页数。请注意,她在阅读之前最多可以应用一次所描述的操作。请注意,答案可以超过 32 位整数。
输入
输入的第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 105)。
下一行包含 m 个由空格分隔的整数:a1, a2, ..., am (1 ≤ ai ≤ n)。
输出
打印一个整数 — Ryouko 需要翻的最少页数。
示例
输入 #1
4 6 1 2 3 4 3 2
输出 #1
3
输入 #2
10 5 9 4 3 8 8
输出 #2
6
注意
第一个样本中,最优解是将第4页合并到第3页,合并后序列a变为{1,2,3,3,3,2},所以Ryouko需要翻的页数为|1 - 2| + |2 - 3| + |3 - 3| + |3 - 3| + |3 - 2| = 3。
在第二个示例中,通过将第 9 页合并到第 4 页来实现最佳解决方案。