该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

lfq成功通过了cl给他出的题目，并且美美得吃，cl见自己的计划没有得逞，恼羞成怒，又给lfq出了一道更难的题目，如果lfq想继续摸金，就必须解决这道题目，他本想拒绝，但是可恶的cl拥有power，使得lfq不得不按他的要求来，你能再次帮帮可怜的lfq吗？

可恶的cl给lfq出了一道购买大红题，具体来说，lfq会进行n轮购买。每轮购买开始之前，lfq会获得1枚哈夫币。哈夫币在每轮购买结束后不会回收，可以保留至下一轮购买。lfq知道，在第i轮（1 ≤ i ≤ n）购买中，花费$c_i$枚哈夫币可以购买一个大红。大红在一轮购买中可以购买任意次。

现在可恶的cl要求lfq回答在这n轮中最多能购买多少个大红？

输入格式

• 第一行，一个正整数n（1 ≤ n ≤ 2 × $10^5$），表示购买轮数。
• 第二行，n个正整数($c_1$,$c_2$,$c_3$.......$c_n$),表示每轮大红的价格，每个正整数不超过$10^9$,

输出格式

• 一行，一个非负整数，表示在这n轮中最多能购买多少个大红？

Samples

6
3 2 5 3 4 3

2

5
6 3 3 4 2

2

5
7 6 5 9 8

0

提示

• 对于第一个样例，lfq可以选择在第2轮与第6轮购买中各购买一个大红。具体过程如下：

  • 获得1枚哈夫币，目前有1枚哈夫币。第1轮购买开始，不购买大红。
  • 获得1枚哈夫币，目前有2枚哈夫币。第2轮购买开始，购买一个大红，目前有0枚哈夫币。
  • 获得1枚哈夫币，目前有1枚哈夫币。第3轮购买开始，不购买大红。
  • 获得1枚哈夫币，目前有2枚哈夫币。第4轮购买开始，不购买大红。
  • 获得1枚哈夫币，目前有3枚哈夫币。第5轮购买开始，不购买大红。
  • 获得1枚哈夫币，目前有4枚哈夫币。第6轮购买开始，购买一个大红，目前有1枚哈夫币。

• 对于第二个样例，lfq可以选择在第5轮购买中购买两个大红。

• 对于第三个样例，lfq无法在这5轮购买中购买大红。

Limitation

1s, 1024KiB for each test case.