← 返回题目列表

AtCoder · codefestival_2016_qualB_d

D. 贪婪的顾客

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

N 人们在高桥店门前排成一排。该人手头现金 i从队伍前面数第 - 个人为正整数 A_i.

店主高桥先生决定了以下方案:他挑选一个产品,设置一个正整数 P 标明其价格,并从队列前面开始按顺序向顾客展示该产品。如下所述重复该步骤。

在每个步骤中,当向客户展示产品时,如果价格 P 等于或小于该客户当时持有的现金,客户购买该产品,高桥先生结束当前步骤。即第一个客户持有的现金符合现金等于或大于 P 减少 P,下一步开始。

高桥先生可以设置正整数的值 P 在每个步骤中独立进行。

他想销售尽可能多的产品。但是,如果客户最终得到 0 购买后手头有现金,那个人就没有回家的车费了。顾客无法回家对高桥先生来说是一个问题,所以他不希望任何人最终 0 现金。

通过编写一个程序来帮助高桥先生,该程序确定在给定每个客户所拥有的初始现金时他可以销售的最大产品数量。

约束

  • 1 ≦ | N | ≦ 100000
  • 1 ≦ A_i ≦ 10^9(1 ≦ i ≦ N)
  • 所有输入均为整数。

输入

输入由标准输入按以下形式提供。

N
A_1
:
A_N

输出

输出一个整数,代表高桥先生可以销售的最大产品数量。


示例输入 1

3
3
2
5

示例输出 1

3

作为值 P,按顺序选择 1, 4, 1.


示例输入 2

15
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9

示例输出 2

18