A plot of land is fenced along the outline of a binary tree. A node is on the boundary if it is any of: the root; a leaf (a node with no children); on the left spine (start at the root and repeatedly move to the left child if it exists, otherwise the right child); or on the right spine (start at the root and repeatedly move to the right child if it exists, otherwise the left child). Report the sum of the values of the distinct boundary nodes, counting each such node exactly once even if it qualifies in several ways.
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 the distinct boundary node values.
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.