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 ai numbered from 1 to n. The goal of the game is to make numbers a1, a2, ..., ak (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 ai > 0 and an integer t (t ≥ 0) such that i + 2t ≤ n. After the values of i and t have been selected, the value of ai is decreased by 1, and the value of ai + 2t 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 ai. 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).

Input

The first input line contains a single integer n. The second line contains n integers ai (0 ≤ ai ≤ 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

Output

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 ai 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.

Examples

Input

4
1 0 1 2


Output

1
1
3


Input

8
1 2 3 4 5 6 7 8


Output

1
3
6
10
16
24
40
import java.io.*;
import java.util.*;
public class A3 {
	
	long[] a, tree, save;
	
	public void solve() throws IOException {
		int n = nextInt();
		a = new long[n + 1];
		tree = new long[5 * n + 1];
		save = new long[5 * n + 1];
		for (int i = 1; i <= n; i++) a[i] = nextLong() + a[i - 1];
		build(1, 1, n);
		long ans = 0;
		for (int i = 1; i < n; i++) {
			long cur = getVal(1, 1, n, i);
			//System.out.println(cur);
			if (cur == 0) {
				writer.println(ans);
				continue;
			}
			int j = 1;
			while (i + j <= n && getMin(1, 1, n, i, i + j - 1) > 0) 
				j <<= 1;
			j >>= 1;
			update(1, 1, n, i, i + j - 1, -cur);
			ans += cur;
			writer.println(ans);
		}
	}
	
	public void build(int i, int l, int r) {
		if (l == r) {
			tree[i] = a[l];
			return;
		}
		int g = (l + r) >> 1;
		int con1 = i << 1;
		int con2 = con1 + 1;
		build(con1, l, g);
		build(con2, g + 1, r);
		up(i, con1, con2);
	}
	
	public long getVal(int i, int l, int r, int pos) {
		if (l == r) return tree[i];
		int g = (l + r) >> 1;
		int con1 = i << 1;
		int con2 = con1 + 1;
		down(i, con1, con2);
		if (pos <= g) return getVal(con1, l, g, pos);
		return getVal(con2, g + 1, r, pos);
	}
	
	public long getMin(int i, int l, int r, int d, int c) {
		if (l == d && r == c) return tree[i];
		int g = (l + r) >> 1;
		int con1 = i << 1;
		int con2 = con1 + 1;
		down(i, con1, con2);
		long ans = 1000000000;
		if (d <= g) ans = Math.min(ans, getMin(con1, l, g, d, Math.min(g, c)));
		if (c > g) ans = Math.min(ans, getMin(con2, g + 1, r, Math.max(g + 1, d), c));
		return ans;
	}
	
	public void update(int i, int l, int r, int d, int c, long v) {
		//System.out.println(i + " " + l + " " + r + " " + d + " " + c);
		if (l == d && r == c) {
			save[i] += v;
			tree[i] += v;
			return;
		}
		int g = (l + r) >> 1;
		int con1 = i << 1;
		int con2 = con1 + 1;
		down(i, con1, con2);
		if (d <= g) update(con1, l, g, d, Math.min(g, c), v);
		if (c > g) update(con2, g + 1, r, Math.max(g + 1, d), c, v);
		up(i, con1, con2);
	}
	
	public void down(int i, int con1, int con2) {
		if (save[i] != 0) {
			save[con1] += save[i];
			tree[con1] += save[i];
			save[con2] += save[i];
			tree[con2] += save[i];
			save[i] = 0;
		}
	}
	
	public void up(int i, int con1, int con2) {
		tree[i] = Math.min(tree[con1], tree[con2]);
	}

	public static void main(String[] args) throws FileNotFoundException {
		new A3().run();
	}

	BufferedReader reader;
	StringTokenizer tokenizer;
	PrintWriter writer;

	public void run() {
		try {
			long tbegin = System.currentTimeMillis();
			reader = new BufferedReader(new InputStreamReader(System.in));
			//reader = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			//writer = new PrintWriter(new FileOutputStream("output.txt"));
			solve();
			//reader.close();
			//System.out.println(System.currentTimeMillis() - tbegin + "ms");
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

	long nextLong() throws IOException {
		return Long.parseLong(nextToken());
	}

	double nextDouble() throws IOException {
		return Double.parseDouble(nextToken());
	}

	String nextToken() throws IOException {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			tokenizer = new StringTokenizer(reader.readLine());
		}
		return tokenizer.nextToken();
	}

}
