Longest Arithmetic Subsequence

Given a sequence of N integers, find the length of the longest arithmetic subsequence. An arithmetic sequence is defined as a sequence where the difference between consecutive elements is constant. The subsequence does not need to be contiguous.

The problem is defined as follows:

Given an integer N and a list of N integers A, find the maximum length of a subsequence of A that forms an arithmetic progression. If N is less than or equal to 2, the answer is simply N since any pair of numbers is trivially arithmetic.

Mathematically, if the arithmetic subsequence is represented as \(a_1, a_2, \dots, a_k\), then it must satisfy the equation:

[ a_{i} - a_{i-1} = d \quad \text{for all} \quad 2 \leq i \leq k, ]

where \(d\) is a constant difference.

This problem can be efficiently solved using dynamic programming with a hash map to track the length of arithmetic sequences ending at each index for various differences.

inputFormat

The input is given from stdin and consists of two lines:

1. The first line contains a single integer N representing the number of elements in the sequence.
2. The second line contains N space-separated integers which represent the sequence.

outputFormat

The output is the length of the longest arithmetic subsequence. This should be printed to stdout.

## sample

5
1 5 7 8 9

3

</p>