You are given a binary tree directly as a level-order array — it is not built by inserting keys one at a time, and parts of it may violate the binary-search-tree property.
The array is parsed with the standard queue-based construction: the first token is the root's value (guaranteed not to be null). Maintain a queue of nodes that still need children assigned, initially containing just the root. Repeatedly take the front node off the queue and consume the next two tokens as its left and right child: a token that is an integer creates a new node (which is pushed onto the queue), while the literal token null means that child is absent (nothing is pushed). Continue until either the token stream or the queue is exhausted; any node whose children would come from tokens past the end of the stream simply has no children.
A subtree (a node together with all of its descendants) is a valid BST if, for every node in it, every value in its left subtree is strictly less than the node's value and every value in its right subtree is strictly greater than the node's value (duplicate values anywhere in the subtree make it invalid). A single leaf node is always a valid BST of size 1.
Find the size (number of nodes) of the largest subtree of the given tree that is a valid BST.
Input format
Line 1: space-separated tokens — the level-order array described above. Each token is either an integer or the literal null.
Output format
A single integer: the size of the largest valid-BST subtree.
Constraints
- The tree has between 1 and 25 real (non-null) nodes.
- Each node value is an integer between -100 and 100 (values may repeat anywhere in the tree).