你在 Bookcase Solidity United (BSU) 工作，这是一家测试家具负载并测量其可靠性的公司。目前，他们正在测试一个有 $n$ 个搁板的书架，搁板从上到下排列。

书架的测试方法是在某些搁板上放置沉重的铱球，并观察它们是否断裂。我们假设所有球都是相同的，且 BSU 有无限多的球。

工程师测量得出，从上往下数第 $i$ 个搁板能承受的球数严格小于 $a_i$。如果搁板上有 $x \ge a_i$ 个球，它就会断裂，球会掉落。如果没有未断裂的搁板，所有的球都会掉到地板上。否则，$\lfloor \frac{x}{2} \rfloor$ 个球会掉到下方最近的未断裂搁板 $j$ 上，其余的球掉到地板上。（不用担心，地板足够坚固，可以承受所有的球。）如果在此操作后，第 $j$ 个搁板上的球数不小于 $a_j$，那么第 $j$ 个搁板也会断裂，球会以同样的方式从该搁板掉落，依此类推。当所有的球都掉到地板上，或者下一个搁板足够坚固以承受掉落到其上的球时，过程终止。

为了测量可靠性，BSU 的员工会逐个在某些搁板上放置球。目标是使用最少数量的球来破坏最上方的 $k$ 个搁板。由于尝试各种放置方案既昂贵又耗时，且沉重的球掉落会产生巨大的噪音，公司管理层要求你计算对于每个从 $1$ 到 $n$ 的 $k$，破坏最上方的 $k$ 个搁板所需的最少球数。

输入格式

第一行包含一个整数 $n$，表示书架上搁板的数量 ($1 \le n \le 70$)。 第二行包含 $n$ 个整数 $a_i$，其中 $a_i$ 是破坏第 $i$ 个搁板所需的最小球数 ($1 \le a_i \le 150$)。搁板从上到下编号。

输出格式

输出 $n$ 个整数。第 $k$ 个整数表示破坏最上方的 $k$ 个搁板所需的最少球数。

样例

样例输入 1

3
8 1 2

样例输出 1

8 8 8

样例输入 2

5
10 3 3 8 4

样例输出 2

10 10 11 17 17

说明

在第一个样例中，我们可以逐个在第一个搁板上放置 8 个球。该搁板肯定会断裂，并且 $\lfloor \frac{8}{2} \rfloor = 4$ 个球会掉到第二个搁板上。第二个搁板现在有 $4 > 1$ 个球，因此它断裂，$\lfloor \frac{4}{2} \rfloor = 2$ 个球掉到第三个搁板上。第三个搁板也断裂了，所有的球都掉到了地板上。因此，答案是 8。

在第二个样例中，为了破坏所有搁板，我们可以先在第三个搁板上放 2 个球，然后在第二个搁板上放 3 个球，之后在第一个搁板上放 10 个球，最后在第四个搁板上放 2 个球。所以，我们总共放置了 $2 + 3 + 10 + 2 = 17$ 个球。