#NC19812. Mountain

Mountain

题目描述

平面上有n座山,每座山都有左右两面,第i座山的高度为ai,现在弱弱在第一座山的左边山脚下(高度为0),他想要依此爬过这些山,到达第n座山的右边山脚下。 除了简单的爬上爬下,还有一种特殊操作。 如果弱弱目前在第 ii 座山右面海拔 xx 的位置,且第 jj 座山(i<ji<j)的高度大于等于 xx,且第 i+1,…,j−1i+1,\ldots,j-1 座山中没有一座山的高度高于 xx,那么他可以使用绳索水平滑到第 jj 座山左面海拔 xx 的位置。 弱弱想找到一种方式,使得行程中海拔变化的总幅度(各段上升、下降幅度之和)最小。请输出最小总幅度。

输入格式

第一行一个整数n(1≤ n≤ 1000)。 接下来一行n个整数ai(1≤ ai≤ 1000)表示每座山的高度。

输出格式

一行一个整数表示答案。

样例 1

5
1 3 5 4 2
10

来源

牛客原题