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
/**
 * Created by IntelliJ IDEA.
 * User: Taras_Brzezinsky
 * Date: 2/29/12
 * Time: 7:52 PM
 * To change this template use File | Settings | File Templates.
 */

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class TaskA extends Thread {
    public TaskA(int type) {
        try {
            if (type == 0) {
                this.input = new BufferedReader(new InputStreamReader(System.in));
                this.output = new PrintWriter(System.out);
            } else {
                this.input = new BufferedReader(new FileReader(INPUT_FILE));
                this.output = new PrintWriter(OUTPUT_FILE);
            }
            this.setPriority(Thread.MAX_PRIORITY);
        } catch (Throwable e) {
            e.printStackTrace();
            System.exit(666);
        }
    }

    class SegmentTree {
        final int n;
        final long[] t;
        final long[] m;
        final boolean[] h;
        final long[] q;

        public SegmentTree(int n) {
            this.n = n;
            t = new long[2 * n];
            m = new long[2 * n];
            h = new boolean[2 * n];
            q = new long[2 * n];
            for (int i = n; i < 2 * n; i++)
                q[i] = 1;
            for (int i = 2 * n - 1; i > 1; i -= 2)
                q[i >> 1] = q[i] + q[i ^ 1];
        }

        void modifierHelper(int i, long p) {
            t[i] += p * q[i];
            m[i] += p;
            h[i] = true;
        }

        void pop(int i) {
            if (h[i >> 1]) {
                t[i >> 1] = t[i] + t[i ^ 1] + m[i >> 1] * q[i >> 1];
            } else {
                t[i >> 1] = t[i] + t[i ^ 1];
            }
        }

        void popUp(int i) {
            for (; i > 1; i >>= 1)
                pop(i);
        }

        void push(int i) {
            if (h[i >> 1]) {
                modifierHelper(i, m[i >> 1]);
                modifierHelper(i ^ 1, m[i >> 1]);
                h[i >> 1] = false;
                m[i >> 1] = 0;
            }
        }

        void pushDown(int i) {
            int k;
            for (k = 0; (i >> k) > 0; k++)
                ;
            for (k -= 2; k >= 0; k--)
                push(i >> k);
        }

        public void modifyAdd(int a, int b, long v) {
            a += n;
            b += n;
            pushDown(a);
            pushDown(b);
            int ta = a;
            int tb = b;

            for (; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
                if ((a & 1) != 0)
                    modifierHelper(a, v);
                if ((b & 1) == 0)
                    modifierHelper(b, v);
            }

            popUp(ta);
            popUp(tb);
        }

        public long querySum(int a, int b) {
            a += n;
            b += n;
            pushDown(a);
            pushDown(b);

            long res = 0;
            for (; a <= b; a = (a + 1) >> 1, b = (b - 1) >> 1) {
                if ((a & 1) != 0)
                    res += t[a];
                if ((b & 1) == 0)
                    res += t[b];
            }
            return res;
        }

        public long get(int i) {
            return querySum(i, i);
        }

        public void set(int i, int v) {
            modifyAdd(i, i, -querySum(i, i) + v);
        }


    }



    private void solve() throws Throwable {
        int n = nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) a[i] = nextInt();
        SegmentTree S = new SegmentTree(n);
        int pw[] = new int[18];
        pw[0] = 1;
        for (int i = 1; i < pw.length; ++i) pw[i] = pw[i - 1] << 1;
        for (int i = 0; i + 1 < n; ++i) {
            int to = pw.length - 1;
            int from = i;
            while (from + 1  < n) {
                for (; to >= 0; --to) {
                    if (from + pw[to] < n) {
                        break;
                    }
                }
                S.modifyAdd(from + 1, n - 1, a[i]);
                from = from + pw[to];
            }
        }
        for (int i = 1; i < n; ++i) output.println(S.get(i));


    }

    public void run() {
        try {
            solve();
        } catch (Throwable e) {
            System.err.println(e.getMessage());
            e.printStackTrace();
            System.exit(666);
        } finally {
            output.flush();
            output.close();
        }
    }

    public static void main(String[] args) {
        new TaskA(0).start();
    }

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

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

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

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

private static final String INPUT_FILE = null;
private static final String OUTPUT_FILE = null;
private BufferedReader input;
private PrintWriter output;
private StringTokenizer tokens = null;
}