Longest Arithmetic Subsequence

Given an array of integers, your task is to determine the length of the longest arithmetic subsequence (LAS). An arithmetic sequence is one in which the difference between consecutive elements is constant. Formally, a sequence \(a_1, a_2, \dots, a_k\) is arithmetic if there exists a constant \(d\) such that \(a_i - a_{i-1} = d\) for all \(2 \le i \le k\).

If the array is empty, the answer is 0. Otherwise, output the maximum possible length of any arithmetic subsequence found in the array.

Example:

Input:
4
3 6 9 12
Output:
4

inputFormat

The input is read from standard input (stdin). The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers. If (n = 0), the second line will be empty.

outputFormat

Output a single integer to standard output (stdout) which is the length of the longest arithmetic subsequence.## sample

4
3 6 9 12

4