Count Good Nodes in Binary Tree

Problem statement

A sensor tree records a value at every station. A station earns a visibility flag when its value is at least every value encountered on the route from the entrance to that station. Your task Count nodes whose value is greater than or equal to the maximum value on their root-to-node path. Important details The root always qualifies because it has no earlier ancestor. Equal values qualify; the comparison is not strict. Track a separate path maximum for each branch, since a large value in a sibling branch must not affect this node. Worked example With root 3 and leaf children 2 and 4, root 3 and child 4 qualify, while child 2 is below its ancestor. The answer is 2.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the number of qualifying nodes.

Constraints

1 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
3 1 2
2 -1 -1
4 -1 -1

Sample output

2