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$轮扫雷中，花费$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$）。

输出格式

一行，一个非负整数，表示最多能购买的地雷探测器数量。

样例

输入：

6  
3 2 5 3 4 3  

输出

2

样例提示

在第二轮购买一个地雷探测器，此时扫雷币变成零，在第六轮，扫雷币变成 $4$ ，可以再购买一个地雷探测器，扫雷币剩余 $1$ ， 无法买到比两个更多的地雷探测器。

数据分布

$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$

$6.10$新增一组数据，$n = 10^7$