Minimum Modifications to Form a Fibonacci Array

An array \(A = (a_0,a_1,\ldots,a_{n-1})\) is called a Fibonacci array if it satisfies the following conditions:

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

You are given an array \(A\) of length \(n\). You are allowed to perform an arbitrary number of modifications. In each modification, you can change the element at any position to any positive integer (greater than 0). Determine the minimum number of modifications required to transform the array \(A\) into a Fibonacci array.

Note: Once the first element \(a_0 = x\) is chosen, the Fibonacci array is uniquely determined as \(a_0 = x,\; a_1 = x,\; a_2 = 2x,\; a_3 = 3x,\; a_4 = 5x,\; a_5 = 8x,\; \ldots\) since it follows the recurrence \(a_i = a_{i-1} + a_{i-2}\) for \(i \ge 2\) with \(x > 0\).

inputFormat

The first line contains a single integer \(n\) (\(n \ge 3\)), the number of elements in the array \(A\). The second line contains \(n\) positive integers separated by spaces representing the elements of \(A\).

outputFormat

Output a single integer: the minimum number of modifications required to transform \(A\) into a Fibonacci array.

sample

5
1 1 2 3 5

0