Longest Divisible Subarray

You are given an array of integers. Your task is to find the length of the longest contiguous subarray in which every pair of consecutive elements satisfies the divisibility condition: the later element is divisible by the previous one. In other words, for a subarray a[l...r] (with r ≥ l), for every i such that l < i ≤ r, it must hold that \(a_i \bmod a_{i-1} = 0\).

Input: The first line contains a single integer \(n\) (the size of the array). The second line contains \(n\) space-separated integers representing the elements of the array.

Output: Print a single integer representing the length of the longest divisible subarray.

Example:

Input:
6
4 2 4 8 16 3
Output:
4

</p>

inputFormat

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

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

outputFormat

Output a single integer on a new line to standard output (stdout) — the length of the longest contiguous subarray where every consecutive pair satisfies that the latter number is divisible by the former.

## sample

6
4 2 4 8 16 3

4

</p>