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<b_m)$ and an integer k which satifies $a_{b_{i+1}}=k\cdot a_{b_i}$ for all $1\le i<m$.
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$