分数: 300 分
问题陈述
冬天,高桥负责铲自家门前路上的积雪。
道路分为 N 部分,从左到右编号为部分 1,部分 2, \ldots,部分 N。断面积雪量 i is A_i 厘米。
高桥使用铲雪机清除积雪。在一次铲雪过程中,他选择了一对整数 (l, r) 满意 1 \leq l \leq r \leq N,并减少部分中每个连续部分的雪量 l 至部分 r by 1 厘米。但是,如果在操作之前,节中的任何节 l, l+1, \ldots, r 有 0 厘米厚的雪,他不能选择那双 (l, r)。铲雪可以进行任意多次,并且他可以选择不同的一对 每次 (l, r) ,或多次选择同一对。
求出使所有路段的雪量准确所需的铲雪次数 0 厘米。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 所有输入均为整数
输入
N A_1 A_2 \ldots A_N
- 第一行包含一个整数 N 代表节数。
- 第二行包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔,代表各部分积雪量。
输出
在一行中打印出使所有路段的雪量精确所需的最少铲雪次数 0 厘米。
示例输入 1
3 3 1 2
示例输出 1
4
示例输入 2
5 2 3 2 1 4
示例输出 2
6
示例输入 3
8 5 0 3 0 8 2 0 1
示例输出 3
17