题目描述

筹备队的酬劳核清后，聪明兔来到会场，查看彩球的准备情况。大笨龙已将彩球分装在一排桶中，自觉井然有序；聪明兔对照布置图，却发现各桶球数还不符合要求。所幸仓库里的彩球十分充足，距离开场也还有一些时间。

一共有 $N$ 个桶，按从左到右的顺序编号为 $1 \sim N$，第 $i$ 个桶里原有 $A_i$ 个球。除此之外，还有无限多个球可以使用。

你可以往每个桶里添加任意数量的球，也可以一个都不添加，但不能取出球或改变桶的顺序。设操作后第 $i$ 个桶里的球数为 $B_i$，需要同时满足：

• 各桶里的球数单调不降，即对于所有 $1 \le i < N$，都有 $B_i \le B_{i+1}$；
• 所有桶里球数的最大公约数大于 $1$，即 $\gcd(B_1, B_2, \ldots, B_N) > 1$。

请你求出至少需要添加多少个球。

输入格式

从文件 balls.in 中读入数据。

第一行包含一个整数 $N$，表示桶的数量。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，表示各桶原有的球数。

输出格式

输出到文件 balls.out 中。

输出一行一个整数，表示至少需要添加的球数。

样例 1

3
11 13 15

3

样例1解释

在每个桶中各添加一个球，球数变为 $12, 14, 16$，满足要求，共添加 $3$ 个球。

样例 2

3
3 1 5

3

样例2解释

在第 $2$ 个桶中添加 $2$ 个球，在第 $3$ 个桶中添加 $1$ 个球，球数变为 $3, 3, 6$，满足要求，共添加 $3$ 个球。

样例3

见附件中的 balls3.in 与 balls3.ans。

样例4

见附件中的 balls4.in 与 balls4.ans。

数据范围

对于所有数据，$1 \le N \le 10^4$，$1 \le A_i \le 10^4$。上述球数上界仅约束初始状态，添加后的球数不受此上界限制。

本题共有 $20$ 个测试点，每个测试点 $5$ 分。

测试点编号	$N \le$	$A_i \le$	特殊性质
$1 \sim 2$	$20$	$1$	无
$3 \sim 6$		$20$
$7$	$1000$	$200$	A
$8 \sim 14$		$1000$	无
$15$	$10^4$		A
$16 \sim 20$			无

特殊性质 A：初始球数单调不降，即对于所有 $1 \le i < N$，均有 $A_i \le A_{i+1}$。

样例附件

下载全部样例（balls-samples.zip）