DÃY SỐ FIBONACCI

Dãy số nguyên a₁, a₂, . . ., a_m được gọi là dãy số Fibonacci nếu thoả mãn một trong các điều kiện sau:

• m = 2,
• a_i+1 = a_i + a_i-1 với m > i ≥ 2.

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₁, b₂, . . ., b_n (n ≥ 2) người ta luôn luôn có thể gạch bỏ một số phần tử của dãy để dãy còn lại (giữ nguyên thứ tự trong dãy ban đầu) 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).

Yêu cầu: Cho số nguyên dương n và dãy số nguyên b₁, b₂, . . ., b_n. Hãy tìm cách gạch bỏ ít nhất các phần tử của dãy để nhận được dãy Fibonacci.

Dữ liệu: Vào từ file văn bản GFIB.INP:

• Dòng đầu tiên chứa số nguyên n (2 ≤ n ≤ 1 000);
• Dòng thứ hai chứa n số nguyên b₁, b₂, . . ., b_n (|b_i| ≤ 10⁶_, 1 ≤ i ≤ n ).

Các số trên một dòng cách nhau bởi dấu cách.

Kết quả: Ghi ra file văn bản GFIB.OUT số lượng ít nhất các phần tử cần gạch bỏ.

GFIB.INP	GFIB.OUT
11 5 -2 50 3 1 4 5 60 9 14 23	2

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 2 ≤ n ≤ 100.

TEST