問題文

数列 $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$ に含まれる要素の種類数は最小で何種類になりますか？

制約

• $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$ の要素の種類数は $2$ 種類になります。
$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