A relay network is laid out as a binary tree rooted at the base station. Each tower has an integer height. A tower is visible if, along the unique path from the base station down to that tower, no earlier tower on the path is strictly taller than it. Equivalently, a tower is visible when its height is greater than or equal to the maximum height among its ancestors. The base station itself is always visible.
Report how many towers are visible.
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 height or null for a missing child. Children of null nodes are omitted.
Output format
A single integer: the number of visible towers.
Constraints
- The tree has between 1 and 2000 nodes (the root is always present).
- Each height is between -1000000 and 1000000.