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;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vii;
typedef vector<char> vci;
typedef pair<ll, ll> pii;
typedef vector< pii > vpi;
typedef vector< vii > vvi;

#define present(container, element) (container.find(element) != container.end())
#define tr(container, it) for(decltype(container.begin()) it = container.begin(); it != container.end(); it++)
#define F(i, m, n) for(int(i) = m; i < n; ++i)
#define FR(i, k, n) for(int(i) = n-1; i >= k; --i)
#define f(i, n)  F(i, 0, n)
#define fr(i, n) FR(i, 0, n)
#define p1(x) cout << x <<"\n";
#define p2(x,y) cout << x << " " << y << "\n";
#define p3(x,y,z) cout << x << " " << y << " " << z << "\n";
#define o1(x) cin >> x;
#define o2(x,y) cin >> x >> y;
#define o3(x,y,z) cin >> x >> y >> z;
#define pi 3.1415926535897932384626
#define mod 1000000007
#define all(a)  (a).begin(), (a).end()
#define rall(a)  (a).rbegin(), (a).rend()
#define pb push_back
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof(a))              //set elements of array to some value
#define siz 256
#define bc(n) __builtin_popcountll(n)
#define leadzero(a) __builtin_clz(a)        // count leading zeroes
#define trailzero(a) __builtin_ctz(a)       // count trailing zeroes
#define bitcount(a) __builtin_popcount(a)   // count set bits
#define lps(v,x) (lower_bound(all(v),x)-v.begin())
#define ups(v,x) (upper_bound(all(v),x)-v.begin())
#define ff first
#define ss second
#define mp(a,b) make_pair(a, b)
#define ppb pop_back
#define sz(a) a.size()
#define ins insert

ll ESP=1e18;
//#########################################################################################
bool isPrime[1000000];
void sieve(long long int N)
{
    for(ll i = 0; i <= N; ++i)
    {
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i)
    {
        if(isPrime[i] == true)
        {
            for(int j = i * i; j <= N ; j += i)
                isPrime[j] = false;
        }
    }
}

//#########################################################################################
bool anagram(char *s1, char *s2)
{
    ll count[siz];
    mem(count,0) ;
    ll i;
    for (i = 0; s1[i] && s2[i];  i++)
    {
        count[s1[i]]++;
        count[s2[i]]--;
    }
    if (s1[i] || s2[i])
    {
        return false;
    }
    F(i,0,siz)
    {
        if (count[i])
        {
            return false;
        }
    }
    return true;

}
//###########################################################################################
int find_largest_digit(int n)
{
    int mx = 0 ;
    while(n>0)
    {
        mx = max(mx, n%10) ;
        n/=10 ;
    }
    return mx  ;
}
//###########################################################################################
ll no_of_digits(ll n)
{
    ll ans = 0 ;
    while(n>0)
    {
        ans++ ;
        n/=10 ;
    }
    return ans ;
}
//###########################################################################################
// modulo Multiplication
ll moduloMultiplication(ll  a, ll  b,  ll  zz)
{
    ll res = 0;
    a %= zz;
    while (b)
    {
        if (b & 1)
            res = (res + a) % zz;

        a = (2 * a) % zz;

        b >>= 1;
    }
    return res;
}
//###########################################################################################
ll to_int(string s)
{
    bool o = true ;
    ll ans = 0 ;
    for(ll i=0; i<s.length(); i++)
    {
        ans = ans*10 + (s[i]-48) ;
    }
    return ans ;
}
//###########################################################################################
//function to calculate a^b under mod...
inline ll powmod(ll x, ll n, ll m)
{
    if(n==0 || x==1)
        return 1;
    else if(n%2==0)
    {
        return powmod((x*x)%m,n/2,m);
    }
    else
    {
        return x*(powmod((x*x)%m,(n-1)/2,m))%m;
    }
}
//###########################################################################################
ll poww(ll a,ll b)
{
    if(b==0 || a==1) return 1;
    ll half=poww(a,(b/2));
    if(half<0 || half>ESP) return -1;
    ll full = (half*half);
    if (half != 0 && full / half != half)
    {
        return -1;
    }

    if(b%2)
    {
        if(full*a<0 || full*a>ESP) return -1;
    }
    if(full<0 || full>ESP) return -1;

    if(b%2)
    {
        ll x = a*full;
        if (a != 0 && x / a != full)
        {
            return -1;
        }
        return (x);
    }
    return full;
}
//###########################################################################################
//function to calculate inverse modulo under mod...assuming gcd is 1
ll invmod(ll a,ll modulo)
{
    ll check=powmod(a,modulo-2,modulo) %modulo;
    return check;
}
//###########################################################################################

ll max(ll a,ll b)
{
    if (a>b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,ll b)
{
    if (a<b)
    {
        return a;
    }
    return b;
}
//###########################################################################################
ll min(ll a,int b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll min(int a,ll b)
{
    if (a<b) return a;
    return b;
}
//###########################################################################################
ll max(ll a,int b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
ll max(int a,ll b)
{
    if (a>b) return a;
    return b;
}
//###########################################################################################
//ll gcd(ll a,ll b)
//{
//    if (b==0) return a;
//    return gcd(b,a%b);
//}
//###########################################################################################
//ll lcm(ll a,ll b)
//{
//    return a/gcd(a,b)*b;
//}
//###########################################################################################
void yes()
{
    cout<<"YES"<<"\n";
}
//###########################################################################################
void no()
{
    cout<<"NO"<<"\n";
}
//###########################################################################################
vector<int> factorize(int n)
{
    vector<int> res;
    for (int i = 2; i * i <= n; ++i)
    {
        while (n % i == 0)
        {
            res.push_back(i);
            n /= i;
        }
    }
    if (n != 1)
    {
        res.push_back(n);
    }
    return res;
}
//###########################################################################################
void printDivisors(int n)
{
    for (int i=1; i<=sqrt(n); i++)
    {
        if (n%i == 0)
        {
            if (n/i == i)
                printf("%d ", i);

            else
                printf("%d %d ", i, n/i);
        }
    }
}
//###########################################################################################
int phi(int n)
{
    int result = n;
    for (int p = 2; p * p <= n; ++p)
    {

        if (n % p == 0)
        {

            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }

    if (n > 1)
        result -= result / n;
    return result;
}
//###########################################################################################
bool presents(vii v, int x)
{
    bool flag = false;
    tr(v,it)
    {
        if(*it==x)
            flag = true;
    }
    return flag;
}
//###########################################################################################
ll ncr(ll n, ll r)
{
    if(n<r)
        return 0;
    long long p = 1, k = 1;
    if (n - r < r)
        r = n - r;

    if (r != 0)
    {
        while (r)
        {
            p *= n;
            k *= r;
            long long m = gcd(p, k);
            p /= m;
            k /= m;

            n--;
            r--;
        }
    }
    else
        p = 1;
    return p;
}
//###########################################################################################
int tc(char c)
{
    int k = c -48;
    return k;
}
//###########################################################################################

bool comp(pii a, pii b)
{
    if(a.ff>b.ff) return true;
    else if(a.ff==b.ff) return a.ss<b.ss;
    else return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    cout << fixed << setprecision(10);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);



    int n;
    cin >> n;
    ll arr[n];
    f(i,n) cin >> arr[i];
    ll ans{};
    f(i,n-1)
    {
        ll k = n-i-1;
        k = log(k)/log(2);
        arr[i+poww(2,k)] += arr[i];
        ans += arr[i];
        cout << ans << endl;
    }
    return 0;
}
