P8808 [Lanqiao Cup 2022 National C] Fibonacci Array

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.

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 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.

**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