一家名为 Gumi-Gumi 的工厂致力于制造轮胎。他们的雕刻机负责在轮胎上雕刻凹槽。轮胎有 $N$ 条垂直凹槽，将橡胶划分为 $N+1$ 个垂直区域。在每个垂直区域上进行水平切割，使得组成该垂直区域的所有部分大小相等。该机器可以在一次切割中，在一条直线上对一个或多个（不一定连续的）垂直区域进行切割。

轮胎切割策略的一个示例，对应第三个样例。

最顶部和最底部的线表示完整的水平切割，而第一条和最后一条垂直线是轮胎的边缘。

给你轮胎的形状。你的任务是计算获得该形状所需的最小切割次数。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 100\,000$)。

接下来的 $N+1$ 行，每行包含一个整数 $a_i$ ($1 \le a_i \le 100\,000$)，表示第 $i$ 个垂直区域应该被等分成多少部分。

输出格式

输出的第一行也是唯一的一行，应包含所需的最小切割次数。

子任务

在占总分 20% 的测试数据中，$N$ 不超过 100。

样例

输入样例 1

1
2
5

输出样例 1

5

输入样例 2

2
3
7
14

输出样例 2

15

输入样例 3

9
4
2
4
1
2
2
2
8
4
2

输出样例 3

7