Longest Arithmetic Sequence

Given an array of integers, your task is to determine the length of the longest arithmetic sequence that can be formed from the array. An arithmetic sequence is a sequence of numbers where the difference between consecutive elements is constant. In mathematical terms, a sequence \(a_1, a_2, \dots, a_k\) is arithmetic if there exists a constant \(d\) such that \(a_{i+1} - a_i = d\) for all \(1 \le i < k\).

For example, for the array [1, 7, 10, 13, 14, 19], one of the longest arithmetic sequences is [1, 7, 13, 19], which has a common difference of 6 and a length of 4.

You are required to read the input from stdin and output the answer to stdout.

inputFormat

The first line of input contains an integer \(n\), the number of elements in the array. The second line contains \(n\) space‐separated integers representing the elements of the array.

outputFormat

Output a single integer: the length of the longest arithmetic sequence that can be formed from the array.

6
1 7 10 13 14 19

4