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

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

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

第一行包含一个整数 N（1 \leq N \leq 10^5），表示储物区的数量。

接下来 N 行，包含了 N 个非负整数 A_1, A_2, \dots, A_n（0 \leq A_i \leq 10^5），A_i 表示第 i 个储物区中的待清理货物数量。

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

样例说明

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

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

1. 第1天：选择储物区 1 至 5，清理每个储物区一件货物。状态变为 [1, 3, 0, 1, 2]。
2. 第2天：选择储物区 1 至 2，清理每个储物区一件货物。状态变为 [0, 2, 0, 1, 2]。
3. 第3天：选择储物区 4 至 5，清理每个储物区一件货物。状态变为 [0, 2, 0, 0, 1]。
4. 第4天：选择储物区 2 至 2，清理储物区一件货物。状态变为 [0, 1, 0, 0, 1]。
5. 第5天：选择储物区 2 至 2，清理储物区一件货物。状态变为 [0, 0, 0, 0, 1]。
6. 第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。

月赛差分25年1月