{"code":"gfib","name":"Dãy con Fibonacci","description":"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.\r\n\r\nVí dụ: Các dãy số sau là dãy số Fibonacci:\r\n+ $[5,-2]$\r\n+ $[5,-2,3,1,4,5,9,14,23]$\r\n\r\nVớ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.\r\n\r\nVí 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).\r\n\r\n

Input

\r\n\r\n+ Dòng đầu tiên chứa số nguyên $n \\ (n \\geq 2)$\r\n+ 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 )$.\r\n+ Các số trên một dòng cách nhau bởi dấu cách.\r\n\r\n

Output

\r\n\r\n- 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\n\r\n

Scoring

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 11\r\n 5 -2 50 3 1 4 5 60 9 14 23\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n ```","points":400.0,"partial":false,"time_limit":2.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}