CODE FESTIVAL 2016 qual B

D - Greedy customers


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 700

問題文

高橋商店の前には、N 人の人が 1 列に並んでいます。前から i 人目の人の所持金は正整数 A_i です。

店主の高橋君は、「品物を選んでその価格を表す正の整数 P を設定し、前の人から順にその品物を見せていく」というステップを繰り返します。

各ステップにおいて、各人は、品物を見せられた時、その価格 P が現時点でのその人の所持金以下だった場合その品物を購入し、高橋君の 1 回のステップは終了します。 すなわち、所持金が 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

Score : 700 points

Problem Statement

N people are waiting in a single line in front of the Takahashi Store. The cash on hand of the i-th person from the front of the line is a positive integer A_i.

Mr. Takahashi, the shop owner, has decided on the following scheme: He picks a product, sets a positive integer P indicating its price, and shows this product to customers in order, starting from the front of the line. This step is repeated as described below.

At each step, when a product is shown to a customer, if price P is equal to or less than the cash held by that customer at the time, the customer buys the product and Mr. Takahashi ends the current step. That is, the cash held by the first customer in line with cash equal to or greater than P decreases by P, and the next step begins.

Mr. Takahashi can set the value of positive integer P independently at each step.

He would like to sell as many products as possible. However, if a customer were to end up with 0 cash on hand after a purchase, that person would not have the fare to go home. Customers not being able to go home would be a problem for Mr. Takahashi, so he does not want anyone to end up with 0 cash.

Help out Mr. Takahashi by writing a program that determines the maximum number of products he can sell, when the initial cash in possession of each customer is given.

Constraints

  • 1 ≦ | N | ≦ 100000
  • 1 ≦ A_i ≦ 10^9(1 ≦ i ≦ N)
  • All inputs are integers.

Input

Inputs are provided from Standard Inputs in the following form.

N
A_1
:
A_N

Output

Output an integer representing the maximum number of products Mr. Takahashi can sell.


Sample Input 1

3
3
2
5

Sample Output 1

3

As values of P, select in order 1, 4, 1.


Sample Input 2

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

Sample Output 2

18

Submit提出する