A stadium's seating frame is a binary tree. Assign positions as if the tree were a complete binary tree: the root has position 0, and a node at position p has left child at position 2*p and right child at position 2*p + 1. The width of a level is the number of positions from the leftmost present node to the rightmost present node on that level, inclusive, counting every intermediate position (present or empty).
Report the maximum width over all levels.
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 label or null for a missing child. Children of null nodes are omitted. (Labels do not affect the answer.)
Output format
A single integer: the maximum level width.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each label is between -1000000 and 1000000.