Valid Preorder Traversal of a BST

Given a sequence of integers, determine whether it represents a valid preorder traversal of a binary search tree (BST). In a BST, for any node with value (v), every node in the left subtree must have a value less than (v), and every node in the right subtree must have a value greater than (v). The preorder traversal is defined as visiting the root node first, then recursively visiting the left subtree and finally the right subtree. An empty sequence is considered valid.

inputFormat

A single line containing space-separated integers representing the preorder traversal of a BST. If there are no integers, the line will be empty.

outputFormat

Output a single line containing either "True" if the sequence represents a valid preorder traversal of a BST, or "False" otherwise.## sample

5 2 1 3 6

True