题目描述

数列 $A\ =\ (A_1,\ A_2,\ ...,\ A_N)$ が与えられます。
あなたは次の操作をちょうど $1$ 回行うことができます。

• $2$ 以上の整数 $M$ を $1$ つ選ぶ。その後、$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$

输出格式

答えを出力せよ。

题目大意

给出一个有 $n$ 个非负整数的数列 $A$

现在进行以下的一次操作：

• 将 $A$ 中所有数对一个大于等于2的整数 $M$ 取模，替换掉原来的数

例如 $A=(2,7,4)$ ，取 $M=4$ ，则操作后 $A=(2 \bmod 4,7 \bmod 4,4 \bmod 4)=(2,3,0)$

请问，操作后的数列 $A$ 最少能有多少种不同的数字。

3
1 4 8

2

4
5 10 15 20

1

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$
• 入力される値はすべて整数

Sample Explanation 1

操作で $M\ =\ 3$ を選ぶと $ A\ =\ (1\ \bmod\ 3,\ 4\ \bmod\ 3,\ 8\ \bmod\ 3)\ =\ (1,\ 1,\ 2) $ になり、操作後の $A$ の要素の種類数は $2$ 種類になります。 $A$ の要素の種類数を $1$ 種類にすることはできないので $2$ が答えです。

Sample Explanation 2

操作で $M\ =\ 5$ を選ぶと $A\ =\ (0,\ 0,\ 0,\ 0)$ になり、これが最適です。