题目描述

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

游戏场地是一串长度为 $n$ 的非负整数 $a_{i}$，编号从 $1$ 到 $n$。游戏的目标是用最少的操作次数，使得前 $k$ 个数 $a_{1},a_{2},...,a_{k}$（即序列的某个前缀）都变为零，其中 $k$ 是一个固定值，且 $k < n$。

每次操作可以选择一个整数 $i$（$1 \leq i \leq n$），要求 $a_{i} > 0$，以及一个整数 $t$（$t \geq 0$），要求 $i + 2^{t} \leq 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 \leq k < n$），计算将原序列的前 $k$ 个元素都变为零所需的最小操作次数。

输入格式

第一行包含一个整数 $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}$

输出格式

输出恰好 $n-1$ 行，第 $k$ 行输出将原序列的前 $k$ 个元素 $a_{i}$ 变为零所需的最小操作次数。

请不要在 C++ 中使用 %lld 格式符来读写 64 位整数。建议使用 cin、cout 流，或 %I64d 格式符。

说明/提示

由 ChatGPT 4.1 翻译

样例

4
1 0 1 2

1
1
3

8
1 2 3 4 5 6 7 8

1
3
6
10
16
24
40