A parking structure is modeled as a binary tree, one level of the tree per underground floor. The deepest level (the one farthest from the root) holds the lowest floor's bays. Add up the values written on every node that lies on that deepest level and report the total.

Input format

Line 1: an integer n, the number of tokens on the next line.

Line 2: n space-separated tokens describing a binary tree in level-order (breadth-first). The first token is the root's value. Reading left to right, keep a queue of already-created nodes; for each node taken from the front of the queue, the next two tokens are its left child then its right child, where the token null marks a missing child. Only non-null children are added to the queue. Trailing null tokens for absent children at the deepest level may be omitted. Every node value is an integer.

Output format

A single integer: the sum of all node values on the deepest level.

Constraints

• 1 <= n <= 129
• The tree has at least 1 and at most 40 nodes.
• Each node value is an integer with -1000 <= value <= 1000.

7
3 9 20 null null 15 7

22

1
5

5