Longest Geometric Subsequence

Given a sequence of integers, find the length of the longest subsequence that forms a geometric progression with an integer common ratio. A sequence a₁, a₂, ..., a_k is said to be a geometric progression if there exists a non-zero integer r such that for every i (1 ≤ i < k), a_i+1 = a_i × r. If the input list is empty, the answer is 0. If there is one number, the answer is 1.

Note: The subsequence does not need to be contiguous. The order of the numbers must remain unchanged.

The mathematical formulation: Given an array \( A = [a_1, a_2, \dots, a_n] \), find the maximum \( k \) such that there exists indices \( 1 \le i_1 < i_2 < \cdots < i_k \le n \) and an integer \( r \) satisfying

[ a_{i_{j+1}} = a_{i_j} \times r \quad \text{for all } 1 \le j < k. ]

inputFormat

The first line contains an integer \( n \) (\( n \ge 0 \)) representing the number of elements in the sequence. If \( n > 0 \), the second line contains \( n \) space-separated integers representing the sequence.

outputFormat

Output a single integer: the length of the longest subsequence forming a geometric progression.

## sample

5
1 3 9 27 81

5

</p>