Longest Arithmetic Subsequence

Given an array of integers, your task is to compute the length of the longest arithmetic subsequence. An arithmetic subsequence is a sequence in which the difference between consecutive elements remains constant. In mathematical terms, a subsequence \(a_1, a_2, \dots, a_k\) is arithmetic if for some constant \(d\) it holds that \(a_{i+1} - a_i = d\) for all valid \(i\).

Your solution should read the input from stdin and print the result to stdout.

inputFormat

The input consists of two lines. The first line contains an integer (n), the number of elements in the array. The second line contains (n) space-separated integers.

outputFormat

Output a single integer representing the length of the longest arithmetic subsequence.## sample

6
1 7 10 13 14 19

4