26271번 - LFIS

문제

어떤 정수 수열 $A$의 부분 수열 중, 다음 조건을 가능한 모든 $i$에 대해 만족하는 수열을 FIS(Fibonacci Increasing Subsequence)라 하자.

• $B_{i - 2} + B_{i - 1} \le B_i$

$A$가 주어질 때, 가장 긴 FIS를 구하여라.

입력

첫 번째 줄에 $N$이 주어진다. (2ドル \le N \le 10^6$)

두 번째 줄에 $A$의 값이 순서대로 주어진다. (0ドル \le A_i \le 10^9$)

출력

첫 번째 줄에 가장 긴 FIS의 길이를 출력한다.

제한

노트

$B$가 $A$의 부분수열이라는 것은, 1ドル \le i_1 < i_2 < \cdots < i_{\lvert B \rvert} \le \lvert A \rvert$가 존재해서 1ドル \le j \le \lvert B \rvert$에 대해 $A_{i_j} = B_j$라는 것을 의미한다.