Problem F
コラッツの予想

Picture by mscolly via Flickr.

約100年後、ローター・コラッツはこの関数を数列 $1, 1, 1, \dots , 1$に適用し、$f$ は常に $1$ になることを確認した。 その結果、彼は任意の数列 $a_ i$ に対して $f$ は定値関数になると推測した。この推測は、現在ではコラッツの予想と称され、植物学における有名な未解決問題の1つとして挙げられる（厳格なコラッツの予想では、$f$ がどれだけ多くの値を取るとしても、実部は常に $\frac{1}{2}$ になる）。

あなたは駆け出しの文化人類学者として、この推測を裏付けることにした。与えられた数列 $a_ i$に対して、$f$ が取る値が何種類あるかを計算する。

入力

入力は2行で与えられる。

• 先頭行は $1 \leq n \leq 5 \cdot 10^5$となる整数で、数列の長さを表す。

• 次の行は数列 $a_1, a_2, \dots , a_ n$で、 $1 \leq a_ i \leq 10^{18}$ を満たす。

出力

単一の整数を含む単一行を出力する。これは、与えられた数列に対する関数がとる値の数を表す。

4
9 6 2 4

6

4
9 6 3 4

5