描述

之前的比赛大家了解到鹿鸣被Red_Comet给难住了，鹿鸣不服气，为了找回面子也给Red_Comet出了一道题，用脚趾头想都知道Red_Comet肯定不会，他想请你帮他解决这个问题，你能帮他解决吗？

有两种操作：

1. 从所有正整数中任选一个数字$x(2\leq x )$，并将所有数字全部对$x$ 求余。
2. 从这$n$个数字中任选一些数字，使得它们全部减去一。

问最少进行多少次操作可以让所有数字全部变为 $0$。

这两种操作都需要“任选”。

输入描述

第一行一个正整数n($1\le n \le100000$)。

第二行给n个数字，第i个数字记作$a_i$($0\le a_i \le10^9$)

输出描述

一行一个整数，表示最少操作次数。

样例

输入

5
1 3 0 12 10

输出

2

样例解释

选择$x=3$，先将所有数字对 3 求余，此时数组变为 [1,0,0,0,1]，再选择第一个数字和第五个数字减一，共两次操作可以使得所有数字全部变为 0。