如果数组 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 ≤ n ≤ 10^5，1 ≤ a_i ≤ 10^6。

3
1 1 2

0

3
2 2 4

0

5
1 2 2 4 8

3