题目描述

某调度中心负责对城市内的 $N$ 条平行输电线缆进行电压调度。这些线缆从左至右依次编号为 $1$ 到 $N$。初始时，所有线缆的输出电压均为 $0$ 千伏。

为满足不同区域的用电需求，线缆 $i$ 最终需要稳定在电压 $v_i$ 千伏。为此，调度中心配备了一套“区间升压装置”：每天可启动一次，每次工程师可任选一个连续区间 $[L, R]$（$1 \leq L \leq R \leq N$），使该区间内所有线缆的输出电压同时提升 $1$ 千伏。

现给定目标电压序列 $v_1, v_2, \cdots, v_N$，请你计算，至少需要多少天，才能使每条线缆的电压恰好达到对应的目标值？

输入格式

第一行一个整数 $N$，表示输电线缆的数量。

第二行包含 $N$ 个整数 $v_1, v_2, \cdots, v_N$，其中 $v_i$ 表示第 $i$ 条线缆需要达到的目标电压（单位：千伏）。

输出格式

输出一行一个整数，表示使所有线缆电压恰好达到目标值所需的最少天数。

4
1 2 1 2

3

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \leq N \leq 10^3$；

对于 $100\%$ 的评测用例，$1 \leq N \leq 10^5$，$0 \leq v_i \leq 10^9$。