A logging tool emits a sequence of distinct integer keys claimed to be the preorder traversal (root, then left subtree, then right subtree) of some binary search tree. Decide whether such a BST exists: is there a BST whose preorder traversal is exactly this sequence?
All keys are distinct, so the BST would use the strict rule (left subtree keys strictly less than the node, right subtree keys strictly greater).
Input format
Line 1: an integer n, the number of keys.
Line 2: n space-separated distinct integers, the claimed preorder sequence.
Output format
Print YES if the sequence is the preorder of some BST, otherwise print NO.
Constraints
- 1 <= n <= 40
- All keys are distinct, each with absolute value <= 1000000.