Dãy số nguyên \(a_1, a_2, . . ., a_m\) được gọi là dãy số Fibonacci nếu thoả mãn: \(a_{i} = a_{i - 1} + a_{i-2}\) với \(i > 2\). Lưu ý rằng dãy có 1 hoặc 2 phần tử thì luôn là dãy Fibonacci.

Ví dụ: Các dãy số sau là dãy số Fibonacci:

• \([5,-2]\)
• \([5,-2,3,1,4,5,9,14,23]\)

Với dãy số nguyên cho trước \(b_1, b_2, ..., b_n\), hãy bỏ đi ít số nhất để dãy còn lại (giữ nguyên thứ tự) là một dãy số Fibonacci.

Ví dụ, từ dãy số cho trước \([5,-2,50,3,1,4,5,60,9,14,23]\), ta có thể nhận được dãy Fibonacci bằng cách gạch bỏ khỏi dãy các phần tử thứ tám (số 60) và phần tử thứ ba (số 50).

Input

• Dòng đầu tiên chứa số nguyên \(n \ (n \geq 2)\)
• Dòng thứ hai chứa \(n\) số nguyên \(b_1, b_2, . . ., b_n (b_i \le 10^9, 1 \le i \le n )\).
• Các số trên một dòng cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên là số lượng ít nhất các phần tử cần gạch bỏ.

Scoring

• Subtask \(1\) (\(91\%\) số điểm): \(n = 11\) đến \(n=100\)
• Subtask \(2\) (\(9\%\) số điểm): \(n \leq 1000\)

Example

11
5 -2 50 3 1 4 5 60 9 14 23

2