Dãy con Fibonacci

Dãy số Fibonacci là một dãy số vô hạn được định nghĩa theo công thức sau: \(F_0 = 0\), \(F_1 = 1\) và \(F_n = F_{n-1} + F_{n-2}\) với \(n \ge 2\). Mỗi số Fibonacci (bắt đầu từ số thứ ba trở đi) bằng tổng của hai số liền kề trước đó. Ví dụ \(10\) số đầu tiên của dãy Fibonacci là: \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34\).

Nam viết lên bảng một số nguyên \(N\) và dãy số nguyên \(a_1, a_2, \ldots, a_N\). Nam muốn biết trong dãy số trên có tồn tại dãy con gồm các số liên tiếp có tổng là số Fibonacci hay không. Nếu có thì độ dài của dãy con dài nhất là bao nhiêu?

Yêu cầu: Hãy tìm độ dài dãy con dài nhất có tổng là số Fibonacci. Nếu không có dãy con nào thỏa mãn thì in ra \(0\).

Input

Dữ liệu vào gồm:

• Dòng thứ nhất chứa số nguyên dương \(N\) (\(1 \le N \le 10^4\));

• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \ldots, a_N\) (\(0 \le a_i \le 10^9\)).

Output

In ra một số nguyên duy nhất là độ dài của dãy con dài nhất tìm được.

Example

Input:

7
3 1 2 4 1 5 4

Output:

5

Note

Dãy con \(1, 2, 4, 1, 5\) (từ phần tử thứ \(2\) đến phần tử thứ \(6\)) có tổng là \(13\), là một số Fibonacci. Không có dãy con liên tiếp nào dài hơn có tổng là số Fibonacci (ví dụ \(3+1+2+4+1+5 = 16\), \(1+2+4+1+5+4 = 17\), cả dãy có tổng \(20\) đều không phải số Fibonacci), nên đáp án là \(5\).