拆分集合

题目描述

给定一个有$n$个数的序列$h_{i}$，下标从$1$开始，且$h_{0}=0$。把$1$~$n$分成两个集合$S_{a}$，$S_{b}$（可以为空），然后再向$S_{a}$和$S_{b}$各加入元素$0$。对于一个集合$S=\{P_{1},P_{2},\cdots,P_{|S|}\}$，其中$\sum_{i=2}^{|S|}|h_{P_{i}}-h_{P_{i-1}}|$，求两个集合的贡献值的和的最小值。

输入格式

第一行为一个正整数$n$。

第二行为$n$个整数$h_{i}$。

输出格式

输出一行非负整数，表示答案。

数据范围与提示

• 对于$50\%$的数据，$n \leq 5000$；
• 对于$100\%$的数据，$1 \leq n$，$h_{i} \leq 5 \times 10^{5}$。

样例

3
1 3 1

4

10
11 45 14 19 19 810 520 1314 258 777

2615

见sprung2.in 

见sprung2.out