花坛浇水

题目描述

一条路上有 $n$ 个花坛排成一排，从左到右编号 $1$ 到 $n$。第 $i$ 个花坛需要被浇水 $h_i$ 次才算达标，初始时每个花坛的浇水次数都是 $0$。每次浇水可以选择一段任意长的连续区间 $[l, r]$（$1 \le l \le r \le n$），让这个区间内每个花坛的浇水次数都增加 $1$。

请计算让所有花坛都达标最少需要浇多少次水。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $h_1, h_2, \dots, h_n$，保证 $h_i \ge 0$。

输出格式

一行一个整数，表示最少需要的浇水次数。

样例

输入样例

5
2 1 3 0 2

输出样例

6

样例解释

需求量依次为 $2, 1, 3, 0, 2$：第 $1$ 个花坛至少要浇 $2$ 次；第 $3$ 个花坛比第 $2$ 个多需要 $2$ 次；第 $5$ 个花坛比第 $4$ 个多需要 $2$ 次；合计 $6$ 次。

数据范围

$1 \le n \le 2 \times 10^5$，$0 \le h_i \le 10^9$。