Longest Arithmetic Subsequence

Given an array of integers, your task is to determine the length of the longest arithmetic subsequence within the array. An arithmetic sequence is one in which the difference between consecutive elements is constant, i.e., for a sequence (a_1, a_2, \ldots, a_k), there exists a constant (d) such that (a_{i+1} - a_i = d) for all valid (i). Note that if the array contains fewer than 2 elements, the answer should be 0.

inputFormat

The input starts with a single integer (n) (the number of elements in the array) on the first line. The second line contains (n) space-separated integers which represent the array elements.

outputFormat

Output a single integer representing the length of the longest arithmetic subsequence found in the array. If there is no arithmetic subsequence or the array contains less than 2 elements, output 0.## sample

5
3 6 9 12 15

5