Longest Arithmetic Subsequence

Given an array of integers, your task is to find the length of the longest arithmetic subsequence. An arithmetic subsequence is a sequence of numbers where the difference between consecutive elements is the same. In other words, if the subsequence is \(a_1, a_2, \dots, a_k\), then for some constant \(d\), we have \(a_{i+1} - a_i = d\) for all \(1 \leq i < k\).

The subsequence does not need to consist of consecutive elements from the array. Your solution should use dynamic programming to track, for each index, the length of the arithmetic subsequence ending at that index with any given difference.

Note: Use standard input (stdin) for input and standard output (stdout) for output.

inputFormat

The first line contains an integer \(n\) ( 1 \(\leq n \leq 10^5\)), representing the number of elements in the array.

The second line contains \(n\) space-separated integers, which are the elements of the array.

outputFormat

Output a single integer that denotes the length of the longest arithmetic subsequence in the array.

## sample

1
5

1

</p>