/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
数列 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
Score : 300 points
Problem Statement
You are given a sequence A = (A_1, A_2, ..., A_N).
You may perform the following operation exactly once.
- Choose an integer M at least 2. Then, for every integer i (1 \leq i \leq N), replace A_i with the remainder when A_i is divided by M.
For instance, if M = 4 is chosen when A = (2, 7, 4), A becomes (2 \bmod 4, 7 \bmod 4, 4 \bmod 4) = (2, 3, 0).
Find the minimum possible number of different elements in A after the operation.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
3 1 4 8
Sample Output 1
2
If you choose M = 3, you will have A = (1 \bmod 3, 4 \bmod 3, 8 \bmod 3) = (1, 1, 2), where A contains two different elements.
The number of different elements in A cannot become 1, so the answer is 2.
Sample Input 2
4 5 10 15 20
Sample Output 2
1
If you choose M = 5, you will have A = (0, 0, 0, 0), which is optimal.
Sample Input 3
10 3785 5176 10740 7744 3999 3143 9028 2822 4748 6888
Sample Output 3
1