← 返回题目列表

AtCoder · pakencamp_2022_day3_i

I. 前缀或

中文机器翻译题面 查看原题

配点 : 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