Maximum Path Sum

Problem Statement

You are given a complete binary tree consisting of $n$ nodes of non-negative integers.

Find the maximum sum of all root-to-leaf paths.

Input

Your first line will contain $n$.

Your next line will contain $n$ numbers, representing the complete binary tree.

Output

The maximum sum of all root-to-leaf paths.

Constraints

For all test cases:

• $0 \le n \le 10^6$
• Each node value, $n_i$, is restricted between $0 \le n_i \le 10^6$.

Example 1

3
4 6 5

10

Example 2

6
5 3 7 11 4 2

19

Example 3

0

0

Python Template

n = int(input())
tree = list(map(int, input().split()))