Longest Arithmetic Subsequence

You are given a sequence of integers. Your task is to determine the length of the longest arithmetic subsequence in the array.

An arithmetic subsequence is a subsequence in which the difference between consecutive elements is constant. Formally, a sequence \( a_1, a_2, \dots, a_k \) is arithmetic if for all \( 2 \le i \le k \), \( a_i - a_{i-1} = d \) for some constant \( d \). Note that the elements in the subsequence do not have to be contiguous in the original sequence.

Input/Output Format: The input is given via standard input and the output should be sent to standard output as described below.

inputFormat

The first line contains an integer \( n \) representing the number of elements in the sequence. The second line contains \( n \) space-separated integers representing the sequence. If \( n = 0 \), then the sequence is empty.

outputFormat

Output a single integer, which is the length of the longest arithmetic subsequence found in the given sequence.

5
3 6 9 12 15

5