Hide

Problem C
Fake Arithmetic Sequence

This problem has nothing to do with Arithmetic Sequence, but I thought it did, hence the name.

You’re given a sequence $a$ of length $n$ containing only integers. Find the longest subsequence $b$ of $a$ such that for all $3 \leq i \leq length(b)$, $b[i] = b[i-1] + b[i-2]$ (Elements of $b$ are enumerated starting from 1).

The sequence $b$ is a subsequence of sequence $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements.

Input

The first line contains a single integer $n$ ($ 1 \leq n \leq 500$).

The second line contains $n$ integers $a_ i$ ($ -10^9 \leq a_ i \leq 10^9$).

Output

A single integer - the length of the longest subsequence $b$

Sample Input 1 Sample Output 1
7
0 3 20 6 20 9 40
4
Sample Input 2 Sample Output 2
7
36 86 -74 39 -99 71 66
2
Sample Input 3 Sample Output 3
10
45 -16 -78 -94 -20 -10 -67 100 -30 -40
4
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
Author
Vuong Hoang Long
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in