# 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 |