Longest Arithmetic Progression Subsequence

Given a sequence of integers, your task is to find the length of the longest arithmetic progression that can be formed by selecting a subsequence from the original sequence. An arithmetic progression is a sequence where the difference between consecutive elements is constant. In mathematical terms, a sequence \(a_1, a_2, \ldots, a_k\) forms an arithmetic progression if there exists a constant \(d\) such that \(a_{i+1} - a_i = d\) for all valid \(i\). This problem requires that you compute the maximum length of such a progression.

You should read the input from the standard input (stdin) and write the output to the standard output (stdout).

inputFormat

The input is given via standard input. The first line contains an integer \(n\) representing the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

Output a single integer representing the length of the longest arithmetic progression subsequence.

6
1 7 10 15 27 29

3