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
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define v(x) vector<x>
#define FOR(i, k, n) for (auto (i) = (k); (i) < (n); (i)++)
#define ROF(i, n, k) for (auto (i) = (n); (i) >= (k); (i)--)
#define FORIT(it, x) for (auto (it) = (x).begin(); (it) != x.end(); (it)++)
#define ROFIT(it, x) for (auto (it) = (x).rbegin(); (it) != x.rend(); (it)++)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define sqr(x) ((ll)(x) * (x))
#define all(x) x.begin(), x.end()
#define endL '\n'
#define deb(x) cout << '>' << #x << ':' << x << endL

#define PI 3.1415926535897932384626

const ll MOD = 1'000'000'007; //998'244'353
const long double EPS = 1e-10;

//print pair
template <class A, class B> ostream& operator<< (ostream& out, const pair<A, B> &a)
{
	return out << '('<< a.F << ", " << a.S << ')';
}
//print vector
template <class A> ostream& operator<<(ostream& out, const vector<A> &v)
{
	out << '[';
	FOR(i, 0, v.size())
	{
		if(i)
			out << ", ";
		out << v[i];
	}
	return out << ']';
}
//input vector
template<class T> istream& operator>>(istream &in, vector<T>& v)
{
    for(auto &e : v)
        in >> e;
    return in;
}

ll add(ll a, ll b)
{
	return ((a % MOD) + (b % MOD)) % MOD;
} 
ll mul(ll a, ll b)
{
	return ((a % MOD) * (b % MOD)) % MOD;
}
ll modpow(ll x, ll pow)
{
	if (!pow)
		return 1;
	ll ans = modpow(x, pow >> 1);
	ans = mul(ans, ans);

	return (pow % 2 ? mul(ans, x) : ans);
}

//--------------------------SOLVE--------------------------//
void solve()
{
	int n;
	cin >> n;
	v(int) a(n);
	cin >> a;
	int t = 1 << (int)log2(n - 1), pre = 0;

	FOR (i, 0, n - 1)
	{
		if (i + t == n)
			t >>= 1;

		pre += a[i];
		a[i + t] += a[i];
		cout << pre << endL;
	}
}
 
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;
 
    // int T;
    // cin >> T;
    // while (T--)
    	solve();
 
	return 0;
}