题目描述

在一家大型仓库中，有 $N$ 个储物区（编号为 $1 \sim N$）。第 $i$ 个储物区中存放着 $A_i$ 件待清理的货物。

仓库配备了一台清洁机器人。每天，机器人可以选择一段编号连续的储物区，并从每个选中的储物区中清理一件货物。

请你帮助仓库管理员计算，最少需要多少天，才能将所有储物区的货物全部清理完毕。

输入格式

输入共 $N + 1$ 行：

• 第一行包含一个整数 $N$，表示储物区的数量。
• 接下来 $N$ 行，每行一个整数 $A_i$，表示第 $i$ 个储物区中的待清理货物数量。

输出格式

输出一个整数，表示最少需要的清理天数。

样例输入

5
2
4
1
2
3

样例输出

6

样例解释

初始状态下，各储物区的货物数量为 [2, 4, 1, 2, 3]。

一种最少清理天数的操作方案如下：

• 第 1 天：选择储物区 1 到 5，状态变为 [1, 3, 0, 1, 2]
• 第 2 天：选择储物区 1 到 2，状态变为 [0, 2, 0, 1, 2]
• 第 3 天：选择储物区 4 到 5，状态变为 [0, 2, 0, 0, 1]
• 第 4 天：选择储物区 2 到 2，状态变为 [0, 1, 0, 0, 1]
• 第 5 天：选择储物区 2 到 2，状态变为 [0, 0, 0, 0, 1]
• 第 6 天：选择储物区 5 到 5，状态变为 [0, 0, 0, 0, 0]

共计 6 天完成清理。

数据范围与约定

• 对于 40% 的数据，满足 $1 \leq N \leq 2000$
• 对于 100% 的数据，满足 $1 \leq N \leq 10^5$，$0 \leq A_i \leq 10^5$