A trellised orchard is arranged as a binary tree; each node is a fruit with an integer weight. The depth of the root is 0 and each child is one deeper than its parent. Consider the deepest level present in the tree (the maximum depth). Report the sum of the weights of all fruits at that deepest level.
Input format
Line 1: an integer k, the number of tokens on line 2.
Line 2: k space-separated tokens giving the tree in level order. The first token is the root; each subsequent token is an integer weight or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the total weight of all fruits at the deepest level.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each weight is between -1000000 and 1000000.