区间得分最小化

题目描述

一个长度至少为 $2$ 的正整数序列的得分，定义为该序列中最大值与最小值之差。

给定一个长度为 $N$ 的正整数序列 $A$。把 $A$ 划分成一个或多个连续子序列，要求每个子序列的长度都至少为 $2$，求所有子序列的得分之和的最小可能值。

形式化地说，求下面式子的最小值：

其中 $K$ 为正整数，$B_1,B_2,\dots,B_K$ 都是长度至少为 $2$ 的正整数序列，且依次拼接 $B_1,B_2,\dots,B_K$ 后恰好得到 $A$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1, A_2, \dots, A_N$。

输出格式

输出一个整数，表示最小的得分之和。

5
1 3 6 8 9

5

样例 1 解释

把 $A$ 划分成 $(1,3)$ 和 $(6,8,9)$，前者的得分为 $3-1=2$，后者的得分为 $9-6=3$，总和为 $5$。

6
1 4 2 8 7 9

5

样例 2 解释

把 $A$ 划分成 $(1,4,2)$ 和 $(8,7,9)$：前者的得分为 $4-1=3$，后者的得分为 $9-7=2$，总和为 $5$，与输出一致。

7
10 480 10 480 480 10 480

470

样例 3 解释

不进行划分，把整个序列作为一个子序列，得分为 $480-10=470$。

数据范围

对于所有测试数据，保证 $2\le N\le 2\times 10^5$，$1\le A_i\le 10^9$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。