在掌握了埃拉托斯特尼筛法（sieve of Eratosthenes）之后，Alice 兴奋地创造了一个利用该算法的益智游戏。游戏规则如下：

• 给定一个数组 $p_1, p_2, \dots, p_n$。初始时，所有 $p_i$ 均为 0。
• 给定一个目标数组 $t_1, t_2, \dots, t_n$。
• 玩家可以执行以下两种操作：
  • 选择 $i$，将所有能被 $i$ 整除的 $j$ 对应的 $p_j$ 加 1。
  • 选择 $i$，将所有能被 $i$ 整除的 $j$ 对应的 $p_j$ 减 1。
• 当经过零次或多次操作后，$p = t$ 时，谜题即告解决。

Alice 的目标是使用最少的操作次数来解决这个谜题，以展示她的解谜技巧。请帮助 Alice 找到解决该谜题所需的最少操作次数。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)。 第二行包含 $n$ 个空格分隔的整数 $t_i$：数组 $t$ 的元素 ($-10^9 \le t_i \le 10^9$)。

输出格式

输出解决该谜题所需的最少操作次数。如果谜题无法解决，输出 -1。

样例

样例输入 1

4
1 1 1 0

样例输出 1

2

样例输入 2

7
0 1 1 1 0 2 -1

样例输出 2

3