CF178A3.Educational Game

The Smart Beaver from ABBYY began to develop a new educational game for children. The rules of the game are fairly simple and are described below.

The playing field is a sequence of n non-negative integers a__i numbered from 1 to n. The goal of the game is to make numbers _a_1, _a_2, ..., a__k (i.e. some prefix of the sequence) equal to zero for some fixed k (k < n), and this should be done in the smallest possible number of moves.

One move is choosing an integer i (1 ≤ i ≤ n) such that a__i > 0 and an integer t (t ≥ 0) such that i + 2_t_ ≤ n. After the values of i and t have been selected, the value of a__i is decreased by 1, and the value of a__i + 2_t_ is increased by 1. For example, let n = 4 and a = (1, 0, 1, 2), then it is possible to make move i = 3, t = 0 and get a = (1, 0, 0, 3) or to make move i = 1, t = 1 and get a = (0, 0, 2, 2) (the only possible other move is i = 1, t = 0).

You are given n and the initial sequence a__i. The task is to calculate the minimum number of moves needed to make the first k elements of the original sequence equal to zero for each possible k (1 ≤ k < n).

ABBYY 的聪明海狸开始为儿童开发一款新的教育游戏。游戏规则非常简单，如下所述。

游戏场地是一个长度为 $n$ 的非负整数序列 $a_i$，下标从 $1$ 到 $n$。游戏目标是：对某个固定的 $k$（其中 $k < n$），使得序列的前缀 $a_1, a_2, \dots, a_k$ 全部变为 $0$，且要求完成该目标所需的移动步数尽可能少。

一次移动定义为：选择一个整数 $i$（满足 $1 \le i \le n$）使得 $a_i > 0$，再选择一个整数 $t$（满足 $t \ge 0$）使得 $i + 2^t \le n$。选定 $i$ 和 $t$ 后，将 $a_i$ 的值减 $1$，同时将 $a_{i + 2^t}$ 的值加 $1$。例如，设 $n = 4$，初始序列为 $a = (1, 0, 1, 2)$，则可执行移动 $i = 3,\, t = 0$，得到新序列 $a = (1, 0, 0, 3)$；也可执行移动 $i = 1,\, t = 1$，得到新序列 $a = (0, 0, 2, 2)$（其余唯一可能的移动是 $i = 1,\, t = 0$）。

现给出 $n$ 及初始序列 $a_i$。任务是：对每个可能的 $k$（$1 \le k < n$），计算使原序列的前 $k$ 个元素全部变为 $0$ 所需的最少移动步数。

The first input line contains a single integer n. The second line contains n integers a__i (0 ≤ a__i ≤ 104), separated by single spaces.

The input limitations for getting 20 points are:

• 1 ≤ n ≤ 300

The input limitations for getting 50 points are:

• 1 ≤ n ≤ 2000

The input limitations for getting 100 points are:

• 1 ≤ n ≤ 105

第一行输入包含一个整数 $n$。第二行包含 $n$ 个整数 $a_i$（$0 \leq a_i \leq 10^4$），以单个空格分隔。

获得 20 分的输入限制为：

• $1 \leq n \leq 300$

获得 50 分的输入限制为：

• $1 \leq n \leq 2000$

获得 100 分的输入限制为：

• $1 \leq n \leq 10^5$

Print exactly n - 1 lines: the k-th output line must contain the minimum number of moves needed to make the first k elements of the original sequence a__i equal to zero.

Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams, or the %I64d specifier.

精确输出 $n-1$ 行：第 $k$ 行输出应为使原序列 $a_i$ 的前 $k$ 个元素均变为零所需的最少操作次数。

在 C++ 中，请勿使用 %lld 说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 说明符。