题目描述

给定一个数列 $A = (A_1, A_2, \ldots, A_N)$。
你可以恰好进行一次如下操作：

• 选择一个不小于 $2$ 的整数 $M$。然后，对于所有满足 $1 \leq i \leq N$ 的整数 $i$，将 $A_i$ 替换为 “$A_i$ 除以 $M$ 的余数”。

例如，当 $A = (2, 7, 4)$ 并选择 $M = 4$ 时，操作后的 $A$ 变为 $(2 \bmod 4, 7 \bmod 4, 4 \bmod 4) = (2, 3, 0)$。

请问，经过操作后，$A$ 中元素的不同种类数最少可以是多少？

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

样例 1

输入

3
1 4 8

输出

2

样例 2

输入

4
5 10 15 20

输出

1

样例 3

输入

10
3785 5176 10740 7744 3999 3143 9028 2822 4748 6888

输出

1

说明/提示

限制条件

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

样例解释 1

如果选择 $M = 3$，则 $A = (1 \bmod 3, 4 \bmod 3, 8 \bmod 3) = (1, 1, 2)$，操作后 $A$ 的元素种类数为 $2$。无法使 $A$ 的元素种类数变为 $1$，因此答案为 $2$。

样例解释 2

如果选择 $M = 5$，则 $A = (0, 0, 0, 0)$，这是最优的情况。

由 ChatGPT 4.1 翻译