← 返回题目列表

AtCoder · awc0078_b

B. 铲雪次数

中文机器翻译题面 查看原题

分数: 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