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}\). 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:

• \([4,-1]\)

• \([4,-1,3,2,5,7,12,19,31,50]\)

Yêu cầu: Cho dãy số nguyên \(b_1,b_2,…,b_n\). Hãy xóa đi ít số nhất để dãy còn lại (giữ nguyên thứ tự) là một dãy số Fibonacii.

Input

• Dòng đầu tiên chứa số nguyên \(n (2≤n≤1000).\)

• Dòng thứ hai chứa \(n\) số nguyên \(b_1,b_2,...,b_n (b_i≤10^9 ).\)

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

Ràng buộc

• Subtask 1:\( n≤100.\)

• Subtask 2 : \(n≤1000.\)

Sample Input

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

Sample Output

2

Giải thích: Xóa số 50 và 60 dãy thu được: 5 -2 3 1 4 5 9 14 23