Counting Maximal Value Roots in Binary Tree

Given a binary tree root, count and return the number of nodes where its value is greater than or equal to the values of all of its descendants.

Constraints

• n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Counting-Maximal-Value-Roots-in-Binary-Tree

Examples

Example 1

Input

• root =

Output

• answer = 4

Explanation

Since all nodes except for 2 meet the criteria.

Solution