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>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<set>
#include<unordered_set>
#include<list>
#include<bitset>
#include<map>
#include<iterator>
#include<algorithm>
#include<utility>
#include<functional>
#include<numeric>
#include<iomanip>
#include<unordered_map>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define nl "\n"
#define NL co<<nl
#define vd " "
#define F first
#define S second
#define fo(a,b) for(i=a;i<b;i++)
#define Fo(a,b) for(i=a;i>=b;i--)
#define fo1(a,b) for(j=a;j<b;j++)
#define Fo1(a,b) for(j=a;j>=b;j--)
#define fo2(a,b,c) for(i=a;i<=b;i+=c)
#define Fo2(a,b,c) for(i=a;i<=b;i-=c)
#define pb push_back
#define mp make_pair
#define popf pop_front
#define popb pop_back
#define eb emplace_back
#define ins insert
#define sf scanf
#define pf printf
#define all(v)  v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define tc(T) while(T--)
#define vec vector
#define co cout
#define d(x) co<<to_string(x)<<vd<<x<<vd
#define yes co<<"YES\n"
#define no co<<"NO\n"
#define yes2 co<<"Yes\n"
#define no2 co<<"No\n"
#define stol(s) stoll(s,nullptr,10)
#define vl vec<ll>
#define usl unordered_set<ll>
#define ml map<ll,ll>
#define mcl map<char,ll>
#define mllit map<ll,ll>::iterator
#define mplll map<pair<ll,ll>,ll>
#define msl map<string,ll>
#define vpl vec<pair<ll,ll>>
#define sl set<ll>
#define mlb map<ll,bool>
#define vb vec<bool>
#define spll set<pair<ll,ll>>
#define spsl set<pair<string,ll>>
#define slit set<ll>::iterator
#define spllit set<pair<ll,ll>>::iterator
#define in(a,n) fo(0,n){cin>>a[i];}
#define vin(a,n) fo(0,n){cin>>q;a.eb(q);}
#define vsinin(a) {cin>>q;a.pb(q);}
#define vpin(a,n) fo(0,n){cin>>q>>w;a.pb({q,w});}
#define vpout(b,n) fo(0,n){co<<b[i].F<<vd<<b[i].S<<nl;}
#define out(a,n) fo(0,n){cout<<a[i]<<vd;}
#define in2d(a,n,m) fo(0,n){for(j=0;j<m;j++){cin>>a[i][j];}}
#define out2d(a,n,m) fo(0,n){for(j=0;j<m;j++){co<<a[i][j]<<vd;} co<<nl;}
#define outit(s,it) for(it=s.begin();it!=s.end();++it){co<<*it<<vd;}
#define factors(a,n) if(n==1){a.pb(1);} else{fo(1,sqrt(n)+1){if(n%i==0){a.pb(i);if(i!=n/i){a.pb(n/i);}}}sort(all(a));}
#define MX(a) *max_element(a,a+n)
#define MN(a) *min_element(a,a+n)
#define VMX(a) *max_element(all(a))
#define VMN(a) *min_element(all(a))
#define lowb(a,x) (std::lower_bound(a.begin(),a.end(),x)-a.begin())
#define upb(a,x) (std::upper_bound(a.begin(),a.end(),x)-a.begin())
#define beg begin()
#define rbeg rbegin()
#define ren rend()
#define en end()
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a*b/gcd(a,b)
ll T=1,inf=100000000000000000,mod=1000000007;
ld pi=acos(0);
inline ll ncr(ll n,ll r)
{
    ll l=n,f2=1,l2=n-r,i=1,j=1;
    if (r != 0||r!=n)
    {
        while (l2!=0||l!=r)
        {
            i*= l;
            j*= l2;
            ll m = gcd(i,j);
            i/= m;
            j/= m;
            l--;
            l2--;
        }
    }
    else i = 1;
    return i;
}
inline ll dig_sum(ll n) {
    ll v=n,sum=0,i;
    while(v) {
        sum+=v%10;
        v/=10;
    }
    return sum;

}
inline bool ckprime(ll n) {
    if(n%2==0&&n!=2) return 0;
    else if(n==2) return 1;
    else {
        ll v=sqrt(n),flag=1,i;
        for(i=3; i<=v; i+=2) {
            if(n%i==0) {
                flag=0;
                break;
            }
        }
        return flag;
    }

}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //cin >> T;
    while(T--)
    {
        int n,sz=1,ans=0,blag=0,u,mn=0,ev=0,mx=0,mini,i,v,q,p,j,k,w,h,l,m,x,y,on=0,total=0,cc=0,pp=0,flag=0,klag=0,sum=0;
        string s,s1,s2;
        bool ok=false;
        cin>>n;
        vl a;
        vin(a,n);
        fo(0,n-1){
        cc+=a[i];
        v=i+1;
        x=n-v;
        q=log10((ld)x)/log10(2LL);
        w=pow(2,q);
        u=i+w;
        a[u]+=a[i];
        co<<cc<<nl;
        }
        


    }
    return 0;
}


/*If I get WA-
check special cases for 0,1,2...
if it seems in 1200-check special cases or bugs.
if seems 1300/1400/1500 -missed any cases.
if get wa again and again after adding case-Change logic.
*/