Background

Chino really likes trees.

Problem Description

A Chino tree is a full binary tree with a certain property. Specifically, for every non-leaf node in this tree, the value of the right child $(C)$ of its left child $(A)$ is the same as the value of the left child $(D)$ of its right child $(B)$. Also, the subtrees rooted at $C$ and $D$ are exactly the same. Now, Chino wants to know how to walk from the root to any leaf node so that the sum of the node weights along the path is as large as possible.

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

Input Format

The first line contains an integer $n$, which represents the number of levels of the binary tree.

The second line contains $2^n-1$ numbers, which represent the preorder traversal of the binary tree.

Output Format

One line containing one number, which is the maximum possible sum of node weights.

3
6 17 43 55 20 55 38

81

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

159

Hint

A long long savior.

Translated by ChatGPT 5