Hide

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