Longest Beautiful Subsequence

Given a sequence of n integers \(a_1, a_2, \ldots, a_n\), a beautiful subsequence is defined as a subsequence that forms an arithmetic progression, i.e. there exists a constant difference \(d\) such that for every two consecutive elements \(x\) and \(y\) in the subsequence, \(y - x = d\). Your task is to determine the length of the longest beautiful subsequence in the given sequence.

Note: A subsequence is obtained by deleting some or no elements without changing the order of the remaining elements.

For example, for the sequence [1, 5, 9, 13, 17], the whole sequence is an arithmetic progression with common difference 4, so the answer is 5.

inputFormat

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

• The first line contains a single integer \(n\) \( (1 \leq n \leq \text{small})\) representing the number of elements in the sequence.
• The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the sequence elements.

outputFormat

Output a single integer to standard output (stdout) — the length of the longest beautiful subsequence in the given sequence.

## sample

5
1 5 9 13 17

5

</p>