겹겹이 묶은 쇼핑 꾸러미

문제

온라인 쇼핑몰은 상품과 꾸러미를 같은 방식으로 다루는 묶음 할인 행사를 연다. 상품 하나는 정해진 양의 정수 가격을 가진다. 꾸러미 하나는 정확히 두 개의 구성품을 가지며, 각 구성품은 상품 하나이거나 다른 꾸러미 하나다. 전체 구매 대상은 가장 바깥의 상품 또는 꾸러미 하나로 표현된다. 같은 상품을 여러 곳에서 공유하는 구조는 없으며, 각 구성품은 자신이 들어 있는 위치에서 한 번만 계산한다. 꾸러미의 결제 금액은 두 구성품의 결제 금액을 먼저 구한 뒤 정한다. 두 금액 중 큰 금액은 전부 내고, 작은 금액은 절반만 낸다. 작은 금액이 홀수라면 절반에서 소수 부분을 버린다. 따라서 두 구성품의 금액이 A와 B일 때 꾸러미의 결제 금액은 max(A, B) + floor(min(A, B) / 2)다. 두 금액이 같아도 어느 쪽을 절반으로 계산하든 결과는 같다. 이 할인은 각 꾸러미에서 반드시 한 번 적용하며, 적용 여부를 선택하거나 구성품을 다른 꾸러미로 옮길 수는 없다. 안쪽 꾸러미에서 계산한 결제 금액은 바깥 꾸러미에서 하나의 구성품 금액으로 사용한다. 바깥 꾸러미가 안쪽의 개별 상품 가격을 직접 비교하지는 않는다. 계산 과정마다 해당 꾸러미의 작은 금액을 절반으로 줄이고 소수 부분을 버리므로, 모든 상품 가격을 더한 뒤 한꺼번에 할인해서는 안 된다. 쇼핑몰은 이 구조를 정수 나열로 저장한다. 상품은 자신의 가격을 나타내는 양의 정수 하나로 기록한다. 꾸러미는 먼저 0을 기록하고, 첫 번째 구성품의 기록 전체와 두 번째 구성품의 기록 전체를 차례대로 이어 붙여 기록한다. 예를 들어 가격이 14인 상품과 가격이 9인 상품을 묶은 꾸러미의 기록은 0 14 9다. 0은 가격이 아니라 뒤에 두 구성품이 이어진다는 표시다. 입력에는 이러한 규칙으로 만든 완전한 구매 대상 하나가 주어진다. 가장 바깥 대상이 상품 하나뿐인 경우도 있다. 기록을 중간에서 끊거나 남는 정수를 덧붙인 입력은 주어지지 않는다. 기록에 나타나는 구성 관계와 각 단계의 할인 규칙을 그대로 적용하여, 가장 바깥 구매 대상의 최종 결제 금액을 구한다.

입력

첫째 줄에 기록에 포함된 정수의 개수 N이 주어진다. N은 1 이상 19,999 이하의 홀수다.
둘째 줄에 기록을 나타내는 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 0 이상 1,000,000 이하이며, 0은 꾸러미 표시이고 양의 정수는 상품 가격이다.
기록은 지문의 규칙에 맞는 구매 대상 하나를 정확히 표현한다. 가장 바깥 대상에서 어떤 상품으로 내려가는 경로에도 꾸러미가 60개를 초과하여 나타나지 않는다.

출력

가장 바깥 구매 대상의 최종 결제 금액을 정수 하나로 출력한다. 가능한 입력에는 항상 하나의 계산 결과가 존재한다.

5
0 0 14 9 20

29

1
37

37

7
0 0 7 7 0 5 3

13

출처: Devin.KR 자체 제작