题目描述

平面上有 $n$ 座山，每座山都有左右两面，第 $i$ 座山的高度为 $a_i$，现在小理在第一座山的左边山脚下（高度为 $0$ ），他想要依此爬过这些山，到达第n座山的右边山脚下。

除了简单的爬上爬下，还有一种特殊操作。 如果小理目前在第 $i$ 座山右面的海拔 $x$ 的位置，且第 $j ( i < j )$ 座山的海拔大于等于 $x$，且第$i+1,\ldots,j-1$ 座山中没有一座山的海拔高于 $x$，那么他可以使用绳索滑到第 $j$ 座山左面海拔 $x$ 的位置。

小理想找到一种方式，使得他在行程中海拔变化的幅度最小。请输出最小幅度。

输入格式

输入共两行。

第一行一个整数 $n$。

接下来一行 $n$ 个整数 $a_i$ 表示每座山的高度。

输出格式

一行一个整数表示答案。

样例输入输出

样例输入

5
1 3 5 4 2

样例输出

10

数据范围

对于 $100%$ 的数据，保证 $1 \le n \le 1000,1 \le a_i \le 1000$。