I - Prefix Or Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。 A の要素を自由に並び替えることができるとき、以下の値としてありうる最小値を求めてください。

\displaystyle \sum_{k=1}^N(A_1\lor A_2\lor\cdots\lor A_k)

ただし \lor はビット単位 \operatorname{OR} 演算を表します。

ビット単位 \operatorname{OR} 演算とは

非負整数 A,B に対するビット単位 \operatorname{OR} 演算 A\lor B は、以下のように定義されます。

  • A\lor B を二進表記した際の 2^k\,(k\geq0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち少なくとも一方が 1 であれば 1、そうでなければ 0 である。

例えば、3\lor5=7 となります（二進表記すると 010\lor101=111）。

制約

  • 1 \le N \le 2\times 10^5
  • 1 \le A_i \le 2\times 10^5
  • 入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
4 1 2

出力例 1

11

A を (1,2,4) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=1+3+7=11 となります。これが最小です。

入力例 2

3
2 5 6

出力例 2

15

A を (2,6,5) に並べ替えると、(A_1)+(A_1\lor A_2)+(A_1\lor A_2\lor A_3)=2+6+7=15 となります。これが最小です。

入力例 3

4
13 13 13 13

出力例 3

52

入力例 4

6
11 15 10 9 4 12

出力例 4

74