题目内容

塔子哥是一个非常有个性的人，他对待装饰品摆放方式的审美角度很奇特。他认为高度相差比较大的装饰品放在相邻位置会很难看。最近，他正在整理桌子上的一排装饰品，但是发现它们的位置摆放得不太好看。于是，他想对这排装饰品进行整理，可以交换任意两个装饰品的位置任意多次，以便让它们看起来更加美观。

假设当前从左到右 $n$ 个装饰品的高度分别为 $h_1,h_2,…,h_n$ 那么当前这一排装饰品的丑陋值为 $\sum^{n-1}_{i=1} |h_i-h_{i+1}|$ ，其中 $|x|$ 为 $x$ 的绝对值。塔子哥不想他的装饰品看起来很丑陋，他想最小化他的装饰品的丑陋值，请你帮他排一下顺序。

形式化地来讲，有一长为 $n$ 的序列 $a_1,a_2,…,a_n$ ，你可以任意次数地进行交换，每次交换都可以选择任意两个不同的数 $i,j$ ，交换 $a_i,a_j$ 的位置。

假设经过若干次交换后，序列变为 $h_1,h_2,...,h_n$ 其丑陋值为 $\sum^{n-1}_{i=1} |h_i-h_{i+1}|$ ，你需要找出一种交换方式，使得最终序列 $\{h_n\}$ 的丑陋值最小化。

你不需要输出具体交换，只需要输出最终的 $\{h_n\}$ 序列的丑陋值即可。

输入描述

第一行一个整数 $n$ ，表示塔子哥的装饰品数量。

接下来一行 $n$ 个整数 $a_1,a_2,…,a_n$ ，依次表示从左到右 $n$ 个装饰品的高度。

对于所有的数据： $2\le N \le 50000$ ， $0\le a_i \le 10^9$ 。

输出描述

输出第一行一个数，为最优方案的最小丑陋值。

样例

输入

3
3 1 2

输出

2

样例解释 我们可以将3和1交换，得到

1 3 2

然后再将2和3交换，得到

1 2 3

可以证明，此时有最小丑陋值 $|1-2|+|2-3|=2$