AtCoder Beginner Contest 019

C - 高橋くんと魔法の箱


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋くんは魔法の箱を持っています。

この箱に整数を入れるとそれに対応した整数が出てきます。

出てくる整数は入れた整数だけによって決まり、同じ整数を入れると毎回同じ結果が得られます。

高橋くんは任意の整数 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) を満たす。

入力例1

3
1 2 3

出力例1

2

2 を入れた時に出てくる整数は、1 を入れた時に出てくる整数と等しいので、最大で 2 種類の整数が出てきます。


入力例2

4
2 4 8 16

出力例2

1

すべて同じ整数が出てきます。


入力例3

4
2 3 5 7

出力例2

4

出てくる整数が全て違う可能性があります。


Submit提出する