跳台阶 - ROJ

【题目描述】

球场边有 $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

【输出样例】

【提示】

【数据规模和约定】对于10%的数据 $N≤20$ 。对于20%的数据 $N≤100$ 。对于50%的数据 $N≤5000$ 。对于100%的数据 $1≤N≤500000$ 。