Longest Arithmetic Progression Subsequence

You are given a sequence of n integers. Your task is to find the length of the longest subsequence (not necessarily contiguous) that forms an arithmetic progression. An arithmetic progression is a sequence in which the difference between any two consecutive elements is constant.

Input Format: The first line contains an integer n representing the number of elements in the sequence. The second line contains n space-separated integers.

Output Format: Output a single integer that represents the length of the longest arithmetic progression subsequence found in the input sequence.

Example:

Input:
6
3 6 9 12 15 18
Output:
6

</p>

Note: If the sequence contains less than two elements, the answer is the length of the sequence itself.

inputFormat

The input is read from standard input and consists of two lines. The first line is a single integer n, denoting the number of elements. The second line contains n space-separated integers representing the sequence.

outputFormat

Output a single integer to standard output, which is the length of the longest arithmetic progression subsequence.

## sample

6
3 6 9 12 15 18

6

</p>