题目描述

N个台阶按编号排列，高度Hi，地面高度0。将每个台阶恰分入两个集合之一，集合可空。每个集合按编号递增依次访问，花费相邻高度差的绝对值之和，包括地面到集合第一个台阶；空集合花费0。求两次访问总体力最小值。

本题为一本通1744的公开本地训练修订版。

输入

一行N，1≤N≤500000；下一行N个整数Hi，1≤Hi≤10^9。

输出

输出一行最小总体力的精确整数。

输入样例

3
1 3 1

输出样例

4

修订说明

原公式缺绝对值时会望远镜消去，与1,3,1样例4不符；本地明确为绝对差，并保留N5e5、高度1e9全域。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：原公式缺绝对值时会望远镜消去，与1,3,1样例4不符；本地明确为绝对差，并保留N5e5、高度1e9全域。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1744。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共5个测试点，非原站或官方原始数据。总分100分。