题目描述

一段道路有 $n$ 块连续区域，第 $i$ 块下陷深度为 $d_i$。每次操作可以选择一段连续区间 $[L, R]$，将区间内每块区域的下陷深度减少 $1$（前提是深度不为 $0$）。求将所有区域深度变为 $0$ 的最少操作次数。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $d_1, d_2, \ldots, d_n$。

输出格式

一行一个整数，表示最少操作次数。

样例

6
4 3 2 5 3 5

9

提示

$1 \le n \le 100000$，$0 \le d_i \le 10000$