Statement

The rabbit sequence, also known as the Fibonacci sequence, is a sequence of length $n$ denoted as $\left\{ a_n \right\}$ if and only if it satisfies one of the following conditions:

1. $n=1$ or $n=2$;
2. When $n\geqslant 3$, $\forall ~ i\in [3,n]$ satisfies $a_{i-2}+a_{i-1}=a_i$.

Given an array $a$ consisting of positive integers, find the length of the longest consecutive rabbit subsequence of the array $a$ ^[1].

Input

The first line contains an integer $n$ representing the length of the sequence; where $n$ satisfies $1\leqslant n\leqslant 1\times 10^5$

The second line contains $n$ integers $a_i$ representing the number of occurrences of each number in the array; each number satisfies $1 \leqslant a_i \leqslant 1 \times 10^9$.

Output

Output an integer representing the length of the longest consecutive rabbit subsequence of $\left\{ a_n \right\}$.

Samples

8
1 1 1 1 2 3 5 1

5

5
5 2 7 9 16

5

Notes

对于第一组样例最长的连续兔子子序列是 $[1, 1, 2, 3, 5]$，长度为 5。

对于第二组样例最长的连续兔子子序列是 $[5, 2, 7, 9, 16]$，长度为 5。