2582: 孤独一生
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：3
题目描述
下课了，Polo来到球场，但他到了之后才发现.....被放了飞机......
无事可做的他决心找点乐子，比方说......跳台阶......
球场边有N个台阶拍成一行，第i个台阶的高度是Hi(0<Hi<=10^9)，第0个台阶，也就是地面的高度为0。Polo打算把这N个台阶分成两个集合Sa,Sb（可以为空），对于一个台阶集合S={P1,P2,...P|S|}，其中P1<P2<...<P|S|，他需要花费∑|Hpi-Hpi-1|的体力值来完成。
现在他希望两次跳跃所需的总体力值最小，你能帮帮他吗？
输入
第一行一个数N。
第二行N个整数Hi。
输出
一行一个整数，表示最小的总体力值。
样例输入 复制
3
1 3 1样例输出 复制
4提示
对于10%的数据N<=20。
对于20%的数据N<=100。
对于50%的数据N<=5000。
对于100%的数据1<=N<=500000。