Educational Game

题意翻译

给你一个数列，长度为 $n$ ，每次操作可以把一个数中的一个 $1$ 往后移动 $2^t$ 个位置（$t\geq0$），问使前 $k$ 个位置都变为 $0$ 至少需要几次操作。对于每个 $k\ (1\leq k<n)$ 输出一行答案（$1≤n≤2000$）

题目描述

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) $ .

输入输出格式

输入格式

The first input line contains a single integer $ n $ . The second line contains $ n $ integers $ a_{i} $ ( $ 0<=a_{i}<=10^{4} $ ), 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<=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.

输入输出样例

输入样例 #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