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