A power distribution network is a binary tree; each node has a positive integer load. Cutting one wire (removing exactly one parent-child edge) splits the network into two connected pieces. The split score is the product of the total load of the two pieces. Choose the wire to cut so that the split score is maximized, and report that maximum product.
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 a positive integer load or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the maximum split score.
Constraints
- The tree has between 2 and 2000 nodes (so at least one wire exists).
- Each load is between 1 and 100000.