← 返回题目列表

AtCoder · arc100_c

E. 或加最大

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

分数: 700 点

问题陈述

存在一个长度为整数的序列 2^N: A_0, A_1, ..., A_{2^N-1}。 (注意顺序是 0- 已索引。)

对于每个整数 K 满意 1 \leq K \leq 2^N-1,解决以下问题:

  • 让 i 和 j 是整数。找到最大值 A_i + A_j 其中 0 \leq i < j \leq 2^N-1 和 (i or j) \leq K。 在这里, or 表示按位或。

约束

  • 1 \leq N \leq 18
  • 1 \leq A_i \leq 10^9
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
A_0 A_1 ... A_{2^N-1}

输出

打印 2^N-1 行。 在 i第行,打印上面问题的答案 K=i.


示例输入 1

2
1 2 3 1

示例输出 1

3
4
5

对于 K=1,唯一可能的对 i 和 j is (i,j)=(0,1),所以答案是 A_0+A_1=1+2=3.

对于 K=2,可能的对 i 和 j 是 (i,j)=(0,1),(0,2)。 当 (i,j)=(0,2), A_i+A_j=1+3=4。这是最大值,所以答案是 4.

对于 K=3,可能的对 i 和 j 是 (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) 。 当 (i,j)=(1,2), A_i+A_j=2+3=5。这是最大值,所以答案是 5.


示例输入 2

3
10 71 84 33 6 47 23 25

示例输出 2

81
94
155
155
155
155
155

示例输入 3

4
75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32

示例输出 3

101
120
147
156
156
178
194
194
194
194
194
194
194
194
194