34519번 - 바보

문제

바보 나라에서 유일한 천재이자 국왕인 은규가 나라를 다스리고 있다. 바보 나라에서 은규를 제외한 $N$명의 바보가 일렬로 서 있다. 은규는 바보들을 불쌍히 여겨 모든 바보를 자신과 같은 천재로 만드는 정책을 펼치고자 한다. 은규는 각 바보에게 "너는 바보다"라고 알려줄 수 있다.

바보가 은규로 인해 자신이 바보임을 깨닫게 되면, 천재가 되기 위해 수련을 시작한다. 나라에서는 특별조사국을 꾸려 오랜 시간 동안 조사한 결과, 바보들의 수련 패턴은 다음과 같다.

• 수련 시작 조건
  • 은규가 $i$번째 바보에게 "너는 바보다"라고 알려주는 순간, $i$번째 바보는 즉시 자신이 바보임을 깨닫게 된다. $(1 \leq i \leq N)$
  • 바보임을 깨닫게 된 시점부터 $i$번째 바보는 바로 수련을 시작한다.
• 수련 완료 시간
  • $i$번째 바보는 수련 시작 후 $T_i$시간이 지나면 천재가 된다.
• 수련 시간 단축
  • 어떤 $i$번째 바보의 수련 시간이 단축되기 위해서는 아직 수련을 시작하지 않았어야 한다. 즉, 수련을 시작한 이후에는 수련 시간이 단축되지 않는다.
  • 바로 양옆 중 한 명이 이미 천재라면, 천재에게 도움을 받아 필요한 수련 시간은 $\displaystyle \left\lfloor \frac{T_i}{2} \right\rfloor$가 된다.
  • 바로 양옆 두 명 모두 이미 천재라면, 두 천재에게 도움을 받아 필요한 수련 시간은 $\displaystyle \left\lfloor \frac{T_i}{4} \right\rfloor$가 된다.

은규는 각 바보에게 언제 바보라고 알려줄지 자유롭게 결정할 수 있다. 정책에 필요한 비용을 마련하기 위해, 모든 바보가 천재가 될 때까지 필요한 최소 시간을 구하고자 하였다. 은규가 구한 최소 시간을 구해보자.

입력

첫 번째 줄에 정수 $N$이 주어진다.

두 번째 줄에 $T_1, T_2, \cdots, T_N$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 모든 바보가 천재가 될 때까지 걸리는 최소 시간을 출력한다.

제한

• 1ドル \leq N \leq 400,000円$
• 1ドル \leq T_i \leq 10^9$
• $T_i$는 정수이다.

힌트