M - 貢ぎ物 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 600 点

問題文

ペンギンは N 個の正整数 A_1,\ A_2,\ldots,\ A_N が入った箱を持っています。彼はこの箱に対して、以下の操作を 0 回以上好きなだけ行うことができます。

  • 箱から好きな要素を重複を許して 2 つ選び、それらの bit ごとの論理和を箱に加える。選んだ 2 整数は箱に入ったままである。

ペンギンはこの操作を繰り返したあと、持っている箱を kaage にプレゼントすることにしました。

kaage は色んな種類の整数を見るのが好きなので、箱に入っている整数の種類が多ければ多いほど喜びます。

ペンギンは上記の操作を繰り返すことで、箱に入っている整数の種類数をいくつまで増やせるでしょうか？

論理和の定義はこちら を参照してください。

制約

  • 入力は全て整数である。
  • 1\leq N\leq2×10^5
  • 1\leq A_i<2^{20}

入力

入力は以下の形式で標準入力から与えられます。

\(N\)
\(A_1\) \(A_2\) \(\ldots\) \(A_N\)

出力

最終的に箱に入っている整数の種類数の最大値を出力してください。 出力の最後に改行を忘れないでください。

入力例1

2
1 2

出力例1

3

1 と 2 を選んで操作を行うと、箱の中身は \{1,\ 2,\ 3\} になります。 これ以上箱に入っている整数の種類数を増やすことはできないので、答えは 3 です。

入力例2

6
1 4 1 3 1 17

出力例2

9

箱に入っている整数が互いに相異なるとは限りません。

入力例3

10
9321 547 38219 57491 212 8724 59243 8243 39842 982

出力例3

89