Longest Arithmetic Progression Subsequence

You are given a list of integers. Your task is to find the longest subsequence that forms an arithmetic progression. An arithmetic progression is a sequence of numbers where the difference between any two consecutive elements is constant.

If the list is empty or contains only one integer, simply output the list itself.

You should note that the program will receive input from standard input (stdin) and output the result to standard output (stdout). The input will begin with an integer n (which can be 0) denoting the number of elements, followed by n integers separated by spaces. The output should be the longest arithmetic progression found in the list, with its elements separated by a single space.

Note: If there are non-integer elements in the input, a runtime error (or exception) should be triggered as per the specifications, but for the purpose of this contest the input will always be valid integers.

inputFormat

The first line of input contains an integer n (n ≥ 0), indicating the number of elements in the list. The second line contains n space-separated integers.

Example:

7
1 3 6 4 7 8 10

outputFormat

Output a single line containing the longest arithmetic progression from the list. The numbers should be printed in order, separated by a single space.

Example Output:

1 4 7 10

## sample

7
1 3 6 4 7 8 10

1 4 7 10