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.