题目描述

花圃中有 $n$ 株植物，从左到右编号为 $1$ 到 $n$。初始时每株植物的高度都是 $0$。

每次浇水可以选择一个非空连续区间 $[l,r]$，使区间内每株植物的高度都增加 $1$。同一个区间可以被多次选择。

给定每株植物的目标高度 $h_i$，请计算至少需要浇水多少次，才能使每株植物的高度恰好等于其目标高度。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个非负整数 $h_1,h_2,\ldots,h_n$。

输出格式

输出一个整数，表示最少浇水次数。

5
2 2 1 3 1

4

3
0 0 0

0

样例 1 解释

可以依次对 $[1,5]$、$[1,2]$、$[4,4]$、$[4,4]$ 浇水，共四次；少于四次无法达到目标。

样例 2 解释

所有植物已经达到目标，不需要浇水。

数据范围与提示

对于所有测试点：$1\le n\le200000$，$0\le h_i\le10^9$。

共 $20$ 个测试点，每个测试点 $5$ 分，独立计分。以下限制均在完整数据范围的基础上额外成立；未列出的参数仍遵守完整数据范围。

测试点编号	额外规模限制
1—5	$n\le30$
6—10	$n\le2000$
11—20	无额外限制

时间限制：2 秒。内存限制：128 MiB。