题目描述

给定一个序列 $A = (A_1, A_2, ..., A_N)$。
你可以执行以下操作最多一次。

• 选择一个整数 $M$，$M \geq 2$。然后，对于每个整数 $i$（$1 \leq i \leq N$），将 $A_i$ 用 $A_i$ 除以 $M$ 的余数替换。

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

找出操作后 $A$ 中不同元素的最小可能数量。

约束条件

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

输入

从标准输入读取输入数据，输入格式如下：

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

输出

输出结果。

示例输入1

3
1 4 8

示例输出1

2

如果选择 $M = 3$，你会得到 $A = (1 \bmod 3, 4 \bmod 3, 8 \bmod 3) = (1, 1, 2)$，其中 $A$ 包含两个不同的元素。
$A$ 中不同元素的数量不能变为 1，因此答案是 2。

示例输入2

4
5 10 15 20

示例输出2

1

如果选择 $M = 5$，你会得到 $A = (0, 0, 0, 0)$，这是最优解。

示例输入3

10
3785 5176 10740 7744 3999 3143 9028 2822 4748 6888

示例输出3

1