A hanging mobile sculpture is a binary tree of joints. Define the height of a sub-mobile as the number of joints on the longest path from that joint straight down to a dangling end; an empty side has height 0, and a single joint with nothing below it has height 1.
A joint is a tilt fault if the heights of its left and right sub-mobiles differ by more than 1 (that is, their absolute difference is at least 2). Report how many joints are tilt faults.
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 number of tilt-fault joints.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each label is between -1000000 and 1000000.