A ski resort's slope is a binary tree of gates. A zigzag run starts at any gate and repeatedly descends to a child, but the direction must alternate: if you just took a left branch, the next branch must be right, and vice versa. The run may stop at any time. The length of a run is the number of branches taken (edges), so a run that visits a single gate has length 0.
Report the maximum length over all zigzag runs.
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 gate id or null for a missing child. Children of null nodes are omitted. (Ids do not affect the answer.)
Output format
A single integer: the length (in branches) of the longest zigzag run.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each gate id is between -1000000 and 1000000.