1525: [2021 세종 정올 예선 O] 세종이의 보물찾기 2

세종이는 프로그래밍 경진대회 이벤트로 또 다른 보물 찾기를 준비하였다. 
예를 들어 깊이가 3인 보물 지도는 아래와 같이 마지막 깊이를 제외하고 각 보물이 있는 지점에서부터 다음 깊이에 2개씩의 지점 으로  연결되어  있다.  
대회에  참가한  학생은  깊이1에서  시작하여  깊이3으로  연결된  길을  따라  이동할 수 있다.





깊이가 3인 보물 지도의 각 지점에 숨겨진 보물의 양이 왼쪽과 같을 때, 획득할 수 있는 최대 보물의 양은 오른쪽 그림과 같이 7개이다.





보물 지도가 주어질 때, 획득할 수 있는 보물의 양의 최댓값을 출력하는 프로그램을 작성하시오.

첫 번째 줄에는 보물 지도의 깊이 n이 입력된다.


두 번째 줄에는 각각의 지점에 숨겨져 있는 보물의 양(a_i)이 공백을 기준으로 입력된다. 
(1 ≤ n ≤ 20), (1 ≤ a_i ≤ 100)


단, 깊이 1에서의 보물이 있는 지점은 1곳이며, 각 깊이마다 2배씩 늘어난다.
1 <= n <= 20
1 <= a_i <= 100

획득할 수 있는 보물의 최댓값을 출력한다.

3
1 2 3 3 4 1 2

7