题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots,A_N)$。 你可以对 $A$ 进行任意次如下操作：

• 选择一个满足 $1 \leq i \leq N$ 的整数 $i$。对于 $i$ 的每个正约数 $j$，将 $A_j$ 加 $1$。

请判断能否使 $A$ 的所有元素相等；若可以，求出所需的最少操作次数。

输入格式

输入按以下格式从标准输入读入：

• $N$
• $A_1$ $A_2$ $\dots$ $A_N$

输出格式

若能使 $A$ 的所有元素相等，输出一行，为所需的最少操作次数；否则输出 $-1$。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^9$
• 所有输入值均为整数。

3
4 7 4

3

第一次操作选择 $i=3$，得到 $A=(5,7,5)$。 第二次操作选择 $i=3$，得到 $A=(6,7,6)$。 第三次操作选择 $i=3$，得到 $A=(7,7,7)$。 无法以少于三次操作使 $A$ 的所有元素相等，因此答案为 $3$。

5
1 3 4 5 6

5

2
5 2

-1

• 来源：AtCoder ABC 474 F

子任务设置

• 子任务 1（30 分）：$N \le 20$ 且 $A_i \le 20$。
• 子任务 2（30 分）：$N \le 2000$。
• 子任务 3（40 分）：无特殊限制。