1744：跳台阶

【题目描述】

球场边有$N$个台阶排成一行，第$i$个台阶的高度是$H_i(0<H_i≤10^9)$，第$0$个台阶，也就是地面的高度为$0$。Polo打算把这$N$个台阶分成两个集合$S_a,S_b$（可以为空），对于一个台阶集合$S=\\{P_1,P_2,...，P_{|S|}\\}$，其中$P_1<P_2<...<P_{|S|}$，他需要花费 $$\\sum_{i=1}^{|s|}H_{p_i}-H_{p_{i-1}}$$ 的体力值来完成。

现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？

【输入】

第一行一个数$N$。

第二行$N$个整数$H_i$。

【输出】

一行一个整数，表示最小的总体力值。

【输入样例】

3
1 3 1

【输出样例】

4

【提示】

【数据规模和约定】

对于10%的数据$N≤20$。

对于20%的数据$N≤100$。

对于50%的数据$N≤5000$。

对于100%的数据$1≤N≤500000$。