You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小安经营着一家柠檬水摊位，一共营业 $n$ 天。每天开始时，摊位会自动补充1个柠檬（可累积到后续天数使用）。在第 $i$ 天，制作1杯柠檬水需要消耗 $c_i$ 个柠檬（每天可以制作任意多杯）。请问小安在这 $n$ 天里，最多能制作多少杯柠檬水？

输入格式

• 第一行：正整数 $n$（$1 \le n \le 2×10^5$），表示营业的天数。
• 第二行：$n$ 个正整数 $c_1, c_2, ..., c_n$（$1 \le c_i \le 10^9$），其中 $c_i$ 表示第 $i$ 天制作1杯柠檬水所需的柠檬数量。

输出格式

一行，一个非负整数，表示最多 $n$ 天内最多能制作的柠檬水总杯数。

样例

输入：

6  
3 2 5 3 4 3  

输出：

2

样例说明

• 第1天开始时获得1个柠檬，累计1个（不足制作1杯，不制作）。
• 第2天开始时获得1个柠檬，累计2个，当天制作1杯（消耗2个），累计剩余0个。
• 第3天开始时获得1个柠檬，累计1个（不足制作）。
• 第4天开始时获得1个柠檬，累计2个（不足制作）。
• 第5天开始时获得1个柠檬，累计3个（不足制作）。
• 第6天开始时获得1个柠檬，累计4个，当天制作1杯（消耗3个），累计剩余1个。
• 总制作数量为2杯，无法再多制作。

数据范围

• 40% 的数据，满足 $1 \le n \le 100$，$1 \le c_i \le 100$。
• 100% 的数据，满足 $1 \le n \le 2×10^5$，$1 \le c_i \le 10^9$。