Largest valid price tree inside

Problem

A binary tree is given, and it may not be a binary search tree. Find the largest subtree (a node and everything below it) that is a valid binary search tree with distinct keys, and print its number of nodes.

Input, output and limits

Input: Line 1: the tree in level order, keys separated by spaces, with # for a missing child. The children of a missing node are not listed, and trailing # may be left out. A single # is an empty tree.
Output: The size of the largest subtree that is a valid BST.
Constraints: 1 ≤ number of nodes ≤ 300
-1000000 ≤ each key ≤ 1000000

Examples

Example 1

Input

10 5 15 1 8 # 7

Output

Example 2

Input

2 1 3

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

Solve the children first and report four facts to the parent: is it a BST, its size, its smallest key, its largest key.

Hint 2

A node forms a BST when both children do, the left maximum is smaller than the node and the right minimum is larger.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems