Longest Geometric Subarray

You are given an array of integers. Your task is to find the length of the longest contiguous subarray that forms a geometric progression.

A subsequence of consecutive elements is said to form a geometric progression if there exists an integer common ratio \( r \) such that for every consecutive pair \(a_i, a_{i+1}\) in the subarray, it holds that \(a_{i+1} = a_i \times r\). Note that if \(a_i = 0\), the progression is broken, and such pairs cannot be considered.

For example, the array [1, 3, 9, 27, 81, 8, 4, 2] has a longest geometric subarray [1, 3, 9, 27, 81] with common ratio \(3\) and length 5.

Your program should read input from standard input and output the answer to standard output.

inputFormat

The first line contains an integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers representing the array elements.

outputFormat

Output a single integer representing the length of the longest contiguous subarray that forms a geometric progression.## sample

8
1 3 9 27 81 8 4 2

5