Background

Chino loves trees very much.

Problem Description

Chino's tree is a full binary tree with a specific property. For each non-leaf node in this tree, the value of its left child node $(A)$'s right child node $(C)$ is the same as the value of its right child node $(B)$'s left child node $(D)$, and the subtrees under $C$ and $D$ are also identical. Now, Chino wants to know how to travel from the root node to any leaf node such that the sum of the weights of the nodes passed along the way is maximized.

$Orz yky, dyh, wjk, jjy, cxr, gsy, cpy, zcy, tyz, yy, hz, zhr, ygg$

Input Format

The first line contains a number, $n$, representing the number of levels in the binary tree.

The second line contains $2^n-1$ numbers, representing the pre-order traversal of the binary tree.

Output Format

A single line containing a number, representing the maximum sum of node weights.

Sample Input and Output

Sample Input #1

3
6 17 43 55 20 55 38

Sample Output #1

81

Sample Input #2

4
6 20 72 61 26 55 26 7 17 55 26 7 38 7 35

Sample Output #2

159

Notes

The answer requires long long type.

见题面 Input 部分

见题面 Output 部分