圆圈擂台（ringfight）

题目描述

Y 同学有 $n$ 个人围成一个圆圈，第 $i$ 个人的实力为 $a_i$。

接下来会进行恰好 $n-1$ 场比赛，直到只剩下 $1$ 个人为止。每一场比赛都必须从当前圆圈中选择一对相邻的人进行。

若某一场比赛中，参赛两人的实力分别为 $u,v$，则实力较大者获胜，实力较小者出局并离开圆圈；获胜者继续留在圆圈中参与后续比赛。保证任意一场比赛都不会出现平局。

定义这一场比赛的评分为两名参赛者实力之差的绝对值，即 $\vert u-v \vert$。

Y 同学可以自行决定每一场比赛的进行顺序。你的任务是求出：在所有合法的比赛顺序中，$n-1$ 场比赛的评分之和的最小值。

输入格式

第一行包含一个整数 $n$，表示人数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个人的实力。

输出格式

输出一行一个整数，表示最小的评分总和。

样例

样例输入 #1

5
3 2 7 9 1

样例输出 #1

9

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le n \le 10^5$，$1 \le a_i \le 10^9$，且任意两个人的实力互不相同。

• 特殊性质 A：保证对所有 $1 \le i \le n$，都有 $a_i=i$。
• 特殊性质 B：保证序列 $a_1,a_2,\dots,a_n$ 单调递增。