题目描述

有一个长度为 $2^N$ 的整数序列 $A_0,\ A_1,\ ...,\ A_{2^N-1}$。（注意下标从 $0$ 开始）

对于所有满足 $1\leq K\leq 2^N-1$ 的整数 $K$，请解决以下问题：

• 设 $i,j$ 为整数，满足 $0\leq i<j\leq 2^N-1$，且 $(i\ \text{or}\ j)\leq K$，求 $A_i+A_j$ 的最大值。这里 $or$ 表示按位或运算。

输入格式

输入以以下格式从标准输入中给出。

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

输出格式

请输出 $2^N-1$ 行。第 $i$ 行输出 $K=i$ 时上述问题的答案。

样例 1

输入

2
1 2 3 1

输出

3
4
5

样例 2

输入

3
10 71 84 33 6 47 23 25

输出

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

输出

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

说明/提示

限制条件

• $1\leq N\leq 18$
• $1\leq A_i\leq 10^9$
• 所有输入均为整数。

样例解释 1

当 $K=1$ 时，可能的 $(i,j)$ 只有 $(0,1)$，所以答案为 $A_0+A_1=1+2=3$。
当 $K=2$ 时，可能的 $(i,j)$ 有 $(0,1),(0,2)$。当 $(i,j)=(0,2)$ 时，$A_i+A_j=1+3=4$，这是最大值，所以答案为 $4$。
当 $K=3$ 时，可能的 $(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$。

由 ChatGPT 4.1 翻译