如果数组 A=($a_0$,$a_1$,…,$a_{n-1}$) 满足 n>2、$a_0$=$a_1$，并且对所有 i≥2 都有 $a_i$=$a_{i-1}$+$a_{i-2}$，就称它为斐波那契数组。

现在可以任意次修改数组元素，每次把某个位置改成一个大于 0 的整数。求最少修改多少个元素，才能使 A 成为斐波那契数组。

输入格式

第一行一个整数 n。

第二行 n 个整数 $a_0$,$a_1$,…,$a_{n-1}$。

输出格式

输出最少修改的元素个数。

样例输入

5
1 2 2 4 8

样例输出

3

3
1 1 2

0

3
2 2 4

0

5
1 2 2 4 8

3

数据范围

3 ≤ n ≤ $10^{5}$，1 ≤ $a_i$ ≤ $10^{6}$。