Given a sequence \(a_1{\dots}a_n\).
You need to find a subsequence \(a_{b_1},a_{b_2},\dots,a_{b_m}(b_1< b_2<\dots and an integer k which satifies \(a_{b_{i+1}}=k\cdot a_{b_i}\) for all \(1\le i.
Your goal is to maximize \(m\).

Input

First line contains an integer \(n\).

Second line contains \(n\) integers, representing the sequence \(a_1{\dots}a_n\).

Output

An integer representing the maximum value of \(m\).

Constraints

\(1\le n\le 10^5\)

\(-10^5\le a_i\le 10^5\)