题目描述

Chaos 在海边散步，并为自己的朋友们挑选贝壳。

Chaos 知道，回家后她会依次见到自己的朋友：

• 首先是 Anomalia，她会要不超过 $a_1$ 个贝壳；
• 然后是 Belya，他会要不超过 $a_2$ 个贝壳；
• 依此类推，直到最后一个朋友 Nenadeynost，她会要不超过 $a_n$ 个贝壳。

但是，在实际见到每个人之前，Chaos 并不知道这个朋友具体会要多少个贝壳。

Chaos 想把贝壳预先装进若干小盒子中，使得当她见到每个朋友时，都能拿出若干个尚未送出的盒子，盒子中的贝壳总数恰好等于该朋友想要的数量。然后她继续用剩下的盒子满足下一个朋友的要求，直到所有朋友都被满足。

请编写程序 mussels，帮助 Chaos 求出为了保证一定可以做到上述事情，所需盒子的最少数量。

输入格式

输入只有一行，首先是整数 $n$，随后是 $a_1,a_2,\ldots,a_n$。

所有输入数都是正整数，并用空格分隔。

输出格式

输出一个整数，表示所需盒子的最少数量。

数据范围

• $1 \le n \le 20000$；
• $1 \le a_i \le 50000$，其中 $i=1,2,\ldots,n$。

样例 1

输入

1 11

输出

4

样例解释

盒子中贝壳数量可以为：$1,2,4,8$。

样例 2

输入

2 5 3

输出

5

样例解释

盒子中贝壳数量可以为：$1,1,2,3,5$。

样例 3

输入

4 2 1 1 3

输出

6

样例解释

盒子中贝壳数量可以为：$1,1,1,1,2,3$。