当前没有测试数据。

题目描述

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

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

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

输入格式

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

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

输出格式

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

样例 #1

输入

5
2
4
1
2
3

输出

6

数据范围

对于 $40\%$ 的数据，满足 $1 \le N \le 2000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$0 \le A_i \le 10^5$。