Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
51 - Andrew Stankevich's Contest, Warmup - 1003
Fibonacci Subsequence

Time Limit: 5 Seconds      Memory Limit: 32768 KB      Special Judge

A sequence of integer numbers a1 , a2 , ..., an is called a Fibonacci sequence if ai = ai-2+ai-1 for all i=3,4,...,n.

Given a sequence of integer numbers c1 , c2 , ..., cm you have to find its longest Fibonacci subsequence.

Input

There are several test cases in the input. The first line of each case contains m (1 <= m <= 3,000). Next line contains m integer numbers not exceeding 109 by their absolute value.
There is a new line between each case.

Output

On the first line of each case print the maximal length of the Fibonacci subsequence of the given sequence. On the second line print the subsequence itself.
There is a new line between each case.

Example

InputOutput
10
1 1 3 -1 2 0 5 -1 -1 8
5
1 -1 0 -1 -1

Submit    Status