Largest Arithmetic Subsequence

Given a sequence of integers, your task is to find the largest arithmetic subsequence contained in it. An arithmetic subsequence is one where the difference between consecutive elements is constant. Formally, a sequence \(a_1, a_2, \ldots, a_k\) is arithmetic if there exists a number \(d\) such that for every \(1 \le i < k\), \(a_{i+1} - a_i = d\).

You will be given an integer \(n\) representing the number of elements, followed by a line containing \(n\) integers. If there are multiple arithmetic subsequences with the maximum length, you can output any one of them. If the input sequence is empty (i.e. \(n=0\)), print an empty line.

Note: The input is provided via stdin, and the output should be written to stdout. The output should consist of the elements of the found subsequence separated by single spaces.

inputFormat

The first line contains a single integer \(n\), representing the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

Print the largest arithmetic subsequence as space-separated integers on a single line. If the input sequence is empty (\(n=0\)), print an empty line.

## sample

9
1 7 4 6 2 3 5 8 10

4 6 8 10

</p>