Longest Arithmetic Subsequence Length

Given a sequence of integers, your task is to find the length of the longest arithmetic subsequence. An arithmetic subsequence is a subsequence in which the difference between consecutive elements is constant. Formally, a subsequence \(a_1, a_2, \dots, a_k\) is arithmetic if for some integer \(d\), it holds that \(a_{i+1} - a_i = d\) for all \(1 \le i < k\). If the input list is empty, return 0. Note that a single element is considered an arithmetic sequence of length 1.

inputFormat

The input is given via standard input. The first line contains an integer \(n\) representing the number of elements. The second line contains \(n\) space-separated integers.

outputFormat

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

4
3 6 9 12

4