AT_abc019_3 [ABC019C] 高橋くんと魔法の箱

[problemUrl]: https://atcoder.jp/contests/abc019/tasks/abc019_3 高橋くんは魔法の箱を持っています。 この箱に整数を入れるとそれに対応した整数が出てきます。 出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。 高橋くんは任意の整数 $ x $ について、$ x $ を入れた時と $ 2x $ を入れた時に出てくる整数が同じであることに気づきました。 高橋くんが入れた整数が $ N $ 個与えられるので、最大で何種類の整数が出てくるか答えてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ a_1 $ $ a_2 $ .. $ a_N $ - $ 1 $ 行目には、高橋くんが箱に入れる整数の個数 $ N\ (\ 1\ ≦\ N\ ≦\ 10^5) $ が与えられる。 - $ 2 $ 行目には、高橋くんが箱に入れる $ N $ 個の整数が空白を区切りとして与えられる。 - $ 1\ ≦\ a_i\ ≦\ 10^9\ (\ 1\ ≦\ i\ ≦\ N) $ であることが保証される。 - $ i\ ≠\ j $ のとき、$ a_i\ ≠\ a_j $ であることが保証される。

最大で何種類の整数が出てくるかを標準出力に出力せよ。 末尾の改行を忘れないこと。

### 部分点 この問題には部分点が設定されている。 - $ 20 $ 点分のテストケースにおいて、$ 1\ ≦\ N\ ≦\ 3,000 $ を満たす。 - 別の $ 30 $ 点分のテストケースにおいて、$ 1\ ≦\ a_i\ ≦\ 5*10^5\ (\ 1\ ≦\ i\ ≦\ N) $ を満たす。 ### Sample Explanation 1 $ 2 $ を入れた時に出てくる整数は、$ 1 $ を入れた時に出てくる整数と等しいので、最大で $ 2 $ 種類の整数が出てきます。 ### Sample Explanation 2 すべて同じ整数が出てきます。 ### Sample Explanation 3 出てくる整数が全て違う可能性があります。