Problem Description

If an array $A = (a_0,a_1,\cdots,a_{n - 1})$ satisfies the following conditions, it is called a Fibonacci array:

1. $n > 2$.
2. $a_0 = a_1$.
3. For all $i \ge 2$, $a_i = a_{i-1} + a_{i-2}$.

Now, an array $A$ is given. You may perform any number of modifications. In each modification, you change the element at some position in the array to a positive integer greater than $0$. What is the minimum number of elements that need to be modified so that array $A$ becomes a Fibonacci array.

Input Format

The first line contains an integer $n$, representing the number of elements in array $A$.

The second line contains $n$ integers $a_0,a_1,\cdots,a_{n-1}$, where adjacent integers are separated by one space.

Output Format

Output one line containing an integer, representing the minimum number of elements that need to be modified in array $A$ so that $A$ can become a Fibonacci array.

5
1 2 2 4 8

3

Hint

Sample Explanation

Modify the original array to $(1,1,2,3,5)$. At least three elements need to be modified to make it a Fibonacci array.

Scale and Constraints of Test Cases

For all test cases, $3 \le n \le 10^5$, $1 \le a_i \le 10^6$.

Lanqiao Cup 2022 National Contest, Group C, Problem E.

Translated by ChatGPT 5