Longest Arithmetic Subsequence

Given an array of positive integers, your task is to determine the length of the longest subsequence that forms an arithmetic progression. A subsequence is obtained by deleting some or none elements from the array without altering the order of the remaining elements.

An arithmetic progression is a sequence in which the difference between consecutive elements is constant. Mathematically, a sequence \(a_1, a_2, \ldots, a_k\) is arithmetic if \(a_{i+1} - a_i = d\) for all \(1 \leq i < k\), where \(d\) is a constant.

Your program should read from the standard input and output the result to the standard output.

inputFormat

The first line contains a single integer \(n\) representing the number of elements in the array.

The second line contains \(n\) positive integers separated by spaces.

outputFormat

Output a single integer which is the length of the longest arithmetic subsequence.

4
3 6 9 12

4