석유가 넘쳐흘러

욱제는 계곡에서 백숙을 팔아 숭실대학교 근처에 작은 땅을 샀다. 놀랍게도 이 땅의 지하에는 석유가 묻혀 있었다. 욱제는 직접 땅을 파서 석유 분수를 만들기로 했다.

욱수르가 되겠다는 생각에 들뜬 욱제는 다음과 같은 구조로 석유 탱크를 연결하며 땅을 파 내려갔다. 용량이 각각 $W_i$인 N개의 탱크가 N-1개의 파이프로 연결되어 포화 이진 트리(노드가 $2^k-1$개인 이진 트리, k는 1 이상의 자연수) 형태를 이룬다. 자식 탱크가 없는 잎 탱크 $(N+1)/2$개에는 석유를 끌어 올리는 펌프가 하나씩 연결되어 있다. 모든 펌프의 성능은 같아서, 매 단위시간마다 석유를 1만큼 끌어 올린다.

자식 탱크에 석유가 가득 차면 부모 탱크로 석유가 넘쳐 오른다. 한쪽 자식 탱크에서 석유가 올라왔는데 다른 자식 탱크가 아직 가득 차지 않았다면, 석유는 그 탱크로 흘러 들어간다. 두 자식 탱크가 모두 가득 차야 비로소 부모 탱크에 석유가 채워지기 시작한다. 하수구가 두 개인 욕조에서 한 하수구로 물이 역류하는 상황을 생각하면 된다.

시각 0에 모든 탱크는 비어 있고, 펌프는 시각 1부터 작동한다. 석유를 끌어 올리거나 파이프를 통해 석유를 옮기는 데는 시간이 걸리지 않는다. 1번 탱크가 항상 가장 위에 있으며, N번 탱크의 왼쪽과 오른쪽 자식은 각각 2N번, 2N+1번 탱크이다.

욱제가 공인인증서와 씨름하는 동안, 각 탱크가 언제 가득 차는지 알아보자.

욱제는 보수적이어서 각 탱크가 가득 찰 수 있는 가장 빠른 시각만 계산하기로 했다. 석유가 어떻게 흐를지는 하나로 정해지지 않으므로, 가능한 가장 빠른 시각을 구해야 한다.

첫째 줄에 탱크의 개수 N이 주어진다. 양의 정수 k에 대해 N = $2^k-1$이 항상 성립한다. (1 ≤ N ≤ 262,143)

둘째 줄에 1번 탱크부터 순서대로 N개 탱크의 용량 W_i이 주어진다. (1 ≤ W_i ≤ 100,000,000)

1번 탱크부터 순서대로 각 탱크에 석유가 가득 찰 수 있는 가장 빠른 시각을 공백으로 구분하여 출력한다.