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.File;import java.io.FileInputStream;import java.io.FileNotFoundException;
import java.io.IOException;import java.io.InputStream;import java.io.PrintStream;
import java.io.PrintWriter;import java.security.AccessControlException;import java.util.Arrays;
import java.util.TreeMap;import java.util.TreeSet;public class _p000178A3 {static public void main(final String[] args) 
throws IOException{p000178A3._main(args);}
static private class p000178A3 extends Solver{public p000178A3(){singleTest=true;
}@Override public void solve()throws IOException{int n=sc.nextInt();sc.nextLine();
int[]a=Arrays.stream(sc.nextLine().trim().split("\\s+")).mapToInt(Integer::parseInt).toArray();
TreeMap<Integer,TreeSet<Integer>>map=new TreeMap<>();TreeSet<Integer>tmp=new TreeSet<>();
int sum=0;int sum1=0;for(int k=1;k<n;k++){sum+=a[k-1];int far=k+Integer.highestOneBit(n
-k);if(!map.containsKey(far)){TreeSet<Integer>set=new TreeSet<>();map.put(far,set);
}map.get(far).add(k);Integer ck=map.ceilingKey(k);if(ck!=null && ck>k){pw.println(sum);
}else{if(map.containsKey(k)){TreeSet<Integer>set=map.get(k);tmp.clear();set.forEach(v
->{if(map.containsKey(v)){tmp.addAll(map.get(v));}});set.addAll(tmp);for(int v:set)
{sum1+=a[v-1];}}pw.println(sum+sum1);}}}static public void _main(String[]args)throws 
IOException{new p000178A3().run();}}static private class MyScanner{private StringBuilder 
cache=new StringBuilder();int cache_pos=0;private int first_linebreak=-1;private 
int second_linebreak=-1;private StringBuilder sb=new StringBuilder();private InputStream 
is=null;public MyScanner(final InputStream is){this.is=is;}private String charToString(final 
int c){return String.format("'%s'",c=='\n'?"\\n":(c=='\r'?"\\r":String.valueOf((char)c)));
}public int get(){int res=-1;if(cache_pos<cache.length()){res=cache.charAt(cache_pos);
cache_pos++;if(cache_pos==cache.length()){cache.delete(0,cache_pos);cache_pos=0;
}}else{try{res=is.read();}catch(IOException ex){throw new RuntimeException(ex);}
}return res;}private void unget(final int c){if(cache_pos==0){cache.insert(0,(char)c);
}else{cache_pos--;}}public String nextLine(){sb.delete(0,sb.length());int c;boolean 
done=false;boolean end=false;while((c=get())!=-1){if(check_linebreak(c)){done=true;
if(c==first_linebreak){if(!end){end=true;}else{cache.append((char)c);break;}}else 
if(second_linebreak!=-1 && c==second_linebreak){break;}}if(end && c!=first_linebreak 
&& c!=second_linebreak){cache.append((char)c);break;}if(!done){sb.append((char)c);
}}return sb.toString();}private boolean check_linebreak(int c){if(c=='\n'|| c=='\r')
{if(first_linebreak==-1){first_linebreak=c;}else if(c!=first_linebreak && second_linebreak
==-1){second_linebreak=c;}return true;}return false;}public int nextInt(){return 
Integer.parseInt(next());}public long nextLong(){return Long.parseLong(next());}
public boolean hasNext(){boolean res=false;int c;while((c=get())!=-1){if(!check_linebreak(c)
&& c!=' '&& c!='\t'){res=true;unget(c);break;}}return res;}public String next(){
sb.delete(0,sb.length());boolean started=false;int c;while((c=get())!=-1){if(check_linebreak(c)
|| c==' '|| c=='\t'){if(started){unget(c);break;}}else{started=true;sb.append((char)c);
}}return sb.toString();}public int nextChar(){return get();}public boolean eof()
{int c=get();boolean res=false;if(c!=-1){unget(c);}else{res=true;}return res;}public 
double nextDouble(){return Double.parseDouble(next());}}static private abstract class 
Solver{protected String nameIn=null;protected String nameOut=null;protected boolean 
singleTest=false;protected boolean preprocessDebug=false;protected boolean doNotPreprocess
=false;protected PrintStream debugPrintStream=null;protected MyScanner sc=null;protected 
PrintWriter pw=null;private int current_test=0;private int count_tests=0;protected 
int currentTest(){return current_test;}protected int countTests(){return count_tests;
}private void process()throws IOException{if(!singleTest){count_tests=sc.nextInt();
sc.nextLine();for(current_test=1;current_test<=count_tests;current_test++){solve();
pw.flush();}}else{count_tests=1;current_test=1;solve();pw.flush();}}abstract protected 
void solve()throws IOException;protected void run()throws IOException{boolean done
=false;try{if(nameIn!=null && new File(nameIn).exists()){try(FileInputStream fis
=new FileInputStream(nameIn);PrintWriter pw0=select_output();){done=true;sc=new 
MyScanner(fis);pw=pw0;process();}}}catch(IOException ex){}catch(AccessControlException 
ex){}if(!done){try(PrintWriter pw0=select_output();){sc=new MyScanner(System.in);
pw=pw0;process();}}}private PrintWriter select_output()throws FileNotFoundException
{if(nameOut!=null){return new PrintWriter(nameOut);}return new PrintWriter(System.out);
}}}
