Longest Arithmetic Subsequence

Given a sequence of integers, your task is to determine the length of the longest subsequence that forms an arithmetic progression. An arithmetic progression is a sequence in which the difference between consecutive terms is constant. Formally, a subsequence A = [a₁, a₂, \dots, a_k] is arithmetic if for some constant \(d\), we have \(a_{i+1} - a_i = d\) for every valid index i.

If the sequence is empty, the answer is 0; if it contains one element, the answer is 1.

inputFormat

The first line of input contains an integer (n) ((0 \le n \le 10^5)), representing 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 that can be found within the given sequence.## sample

6
3 6 9 12 15 18

6