B. Stop! High School Maths Please No More
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Rubyonly 有一个长度为 $$$n$$$ 的正整数数列 $$$[a_1, a_2, a_3, \cdots, a_n]$$$。

Rubyonly 喜欢等比数列，因此，他打算对这个数列进行若干次修改。

每次修改，Rubyonly 都将选择一对正整数 $$$i$$$ 和 $$$x$$$（$$$1 \leq i \leq n$$$ 且 $$$1 \leq x$$$），并将 $$$a_i$$$ 修改为 $$$x$$$。注意，这里的 $$$x$$$ 可以是任意大的有限正整数。

Rubyonly 希望通过尽可能少的修改次数，将原数列修改成一个公比为正整数的等比数列。

更具体的讲，我们记修改后的数列为 $$$[b_1, b_2, b_3, \cdots, b_n]$$$，需要存在一个正整数 $$$q$$$，使得对于任意的 $$$1 \leq i \leq n-1$$$，都有 $$$b_{i+1} = q \cdot b_i$$$ 成立。

请你帮 Rubyonly 计算一下，他至少需要进行几次修改，才能达成这一目标。

Input

第一行包含一个正整数 $$$n$$$（$$$2 \leq n \leq 10^5$$$），表示原数列的长度。

第二行包含 $$$n$$$ 个正整数 $$$a_1, a_2, a_3, \cdots, a_n$$$（$$$1 \leq a_i \leq 10^{18}$$$），用空格分隔，表示原数列中的数。

Output

输出一行，包含一个整数，表示最少需要的修改次数。

Examples
Input
5
1 3 4 5 16
Output
2
Input
7
1 2 1 2 1 2 1
Output
3
Input
2
2 1
Output
1
Input
4
1 2 16777216 140737488355328
Output
2
Input
3
1 1000000000 999999999999999999
Output
1
Input
3
1 4294967297 8589934593
Output
1
Input
5
1 4 6 8 10
Output
3
Input
5
1 100 10000 1000000 100000000
Output
0
Note

在样例一中，可以通过 $$$2$$$ 次修改，将原数列修改为 $$$[1, 2, 4, 8, 16]$$$。

在样例二中，可以通过 $$$3$$$ 次修改，将原数列修改为 $$$[1, 1, 1, 1, 1, 1, 1]$$$。