Longest Arithmetic Subsequence

You are given an array of n integers. Your task is to compute the length of the longest arithmetic subsequence that can be formed from the array. An arithmetic subsequence is a sequence of numbers with a constant difference between consecutive elements. Formally, an arithmetic sequence satisfies:

\( a_{i+1} - a_i = d \) for some constant \( d \) and all consecutive \( i \).

Note that the subsequence does not need to be contiguous. For example, given the array [1, 7, 10, 13, 14, 19], the longest arithmetic subsequence is [1, 7, 13, 19] with a common difference of 6, and its length is 4.

inputFormat

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

Example:

6
1 7 10 13 14 19

outputFormat

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

Example:

4

## sample

6
1 7 10 13 14 19

4

</p>