Longest Arithmetic Subsequence Length

You are given a sequence of integers. Your task is to find the length of the longest arithmetic subsequence of this sequence. An arithmetic subsequence is a sequence of numbers such that the difference between any two consecutive elements is constant. That is, for a subsequence ( a_1, a_2, \dots, a_k ), there exists a constant difference ( d ) satisfying ( a_{i+1} - a_i = d ) for all ( 1 \le i < k ).

The input will be provided via standard input, and the output should be printed to standard output. If the input sequence is empty, output 0.

inputFormat

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

outputFormat

Output a single integer: the length of the longest arithmetic subsequence in the given sequence.## sample

6
3 6 9 12 15 18

6