A binary tree is given as a single space-separated level-order array. Values appear top-to-bottom, left-to-right; the literal token null marks a missing child (a null never has children). An empty tree is encoded as the single token null.
Levels are numbered from the root: the root is level 0, its children are level 1, and so on. For each level, compute the sum of the values of the nodes on that level. Find the level with the largest such sum. If several levels tie for the largest sum, choose the one with the smallest level index.
Print that level index. If the tree is empty, print -1.
Input format
A single line of level-order tokens separated by single spaces. Each token is an integer or the literal null. The line may be exactly null for an empty tree.
Output format
A single integer: the smallest 0-indexed level whose sum is maximal, or -1 if the tree is empty.
Constraints
- The number of real (non-null) nodes is between 0 and 100000.
- Each node value is in the range -100000 to 100000.
- The input is always a valid level-order serialization.