ABBYY 的智能海狸开始开发一款新的儿童教育游戏。游戏规则相当简单,如下所述。
比赛场地是 n 个非负整数 ai 的序列,编号从 1 到 n。游戏的目标是对于某个固定的 k (k < n),使数字 a1、a2、...、ak(即序列的某个前缀)等于 0,并且这应该以尽可能少的步数完成。
一步是选择一个整数 i (1 ≤ i ≤ n) 使得 ai > 0 和一个整数 t (t ≥ 0) 使得 i + 2t ≤ n。 i 和 t 的值选定后,ai 的值减 1,ai + 2t 的值加 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 和初始序列 ai。任务是计算对于每个可能的 k (1 ≤ k < n),使原始序列的前 k 个元素等于 0 所需的最小移动次数。
输入
第一个输入行包含单个整数 n。第二行包含 n 个整数 ai (0 ≤ ai ≤ 104),用单个空格分隔。
获得 20 点的输入限制为:
- 1 ≤ n ≤ 300
获得 50 点的输入限制为:
- 1 ≤ n ≤ 2000
获得 100 点的输入限制为:
- 1 ≤ n ≤ 105
输出
精确打印 n - 1 行:第 k 个输出行必须包含使原始序列 ai 的前 k 个元素等于 0 所需的最小移动次数。
请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #1
4 1 0 1 2
输出 #1
1 1 3
输入 #2
8 1 2 3 4 5 6 7 8
输出 #2
1 3 6 10 16 24 40