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

Input

3
4 6 5

Output

10

Example 2

Input

6
5 3 7 11 4 2

Output

19

Example 3

Input

0

Output

0

Python Template

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