Description

A database index is stored as a Binary Search Tree (BST). Due to a system error, the index may be corrupted. Validate if the given tree is a valid BST.

Input

Output

Constraints

• •Number of nodes: 1 ~ 10,000
• •Node values: -2^31 ~ 2^31 - 1
• •Left subtree < Root < Right subtree

Examples

[50, 30, 70, 20, 60, 65, 80]

false

[50, 30, 70, 20, 40, 65, 80]

true