17261번 - 석유가 넘쳐흘러

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

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

자식 탱크에 석유가 가득 차면 부모 탱크로 석유가 넘쳐 오른다. 만약 어떤 자식 탱크로부터 석유가 올라왔는데 다른 자식 탱크는 아직 가득 차지 않았다면, 석유는 자연스럽게 다른 자식 탱크로 흘러 들어가게 된다. (욕조에 하수구가 두 개 있고 한 하수구에서 물이 역류했을 때를 생각하면 된다) 두 자식 탱크가 가득 차면, 그제야 비로소 부모 탱크에 석유가 채워지기 시작한다.

시각 0에 모든 연료 탱크는 비어 있고, 펌프는 시각 1부터 작동한다. 펌프가 석유를 끌어 올리거나 파이프를 통해 석유가 이동하는데 걸리는 시간은 0이라고 하자. 가장 위에 있는 꼭대기 탱크의 번호는 항상 1이고, 부모 탱크 번호가 N일 때 좌우 자식 탱크 번호는 각 2×N, 2×N+1이다.

욱제는 이 탱크 구조물을 관리할 4차산업혁명인공지능빅데이터IoT미세먼지친환경5G블록체인스마트시스템을 개발하기로 했다. 그러기 위해서는 각 탱크에 석유가 가득차게 되는 시각을 알아야 한다. 하지만 탱크의 용량도 제각각이고, 석유가 어디로 어떻게 흘러갈 지 모르기 때문에 이러한 시각은 유일하게 결정되지 않을 수 있다. 욱제는 보수적이기 때문에, 각 탱크에 석유가 가득 찰 수 있는 가장 빠른 시각만을 계산하기로 했다.

욱제가 4차산업혁명인공지능빅데이터IoT미세먼지친환경5G블록체인스마트시스템을 개발하기 위해 공인인증서와 싸우는 동안, 탱크가 언제 가득 차게 될지 알아보자!

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

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

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