Preorder Traversals

In a binary search tree, every value in the left subtree of a node is smaller than the value in that node, every value in the right subtree is bigger than it, and every subtree is again a binary search tree. This problem does not deal with empty trees. Nodes can hold any ordered data type, but here they hold positive integers smaller than 1,000,000,000.

A preorder traversal is defined by this pseudocode.

preorder_traversal(root)
    print the value in root
    if root has a left subtree
        preorder_traversal(left subtree of root)
    if root has a right subtree
        preorder_traversal(right subtree of root)

For example, 50, 30, 20, 10, 25, 40, 45, 70, 90, 80 is the preorder traversal of a binary search tree. On the other hand, 2, 3, 1 is not the preorder traversal of any binary search tree. The first printed value, 2, has to be the root. Then 3 is bigger than 2 and goes into the right subtree, while the 1 that follows is smaller than 2 and has to go into the left subtree. A preorder traversal prints the left subtree before the right subtree, so 1 cannot come after 3.

The left side is strictly smaller and the right side is strictly bigger, so a list in which some value appears more than once is not the preorder traversal of any binary search tree.

Read a list of numbers and decide whether it is the preorder traversal of a binary search tree.

The input holds several cases. Each case is a list of positive integers followed by one negative integer that signals the end of the list and is not part of it. A long list may be spread over more than one line. Do not assume any input format beyond integers separated by whitespace. The list holds at least 1 and at most 1,000 numbers. Process the input until end of file.

For each case, print yes if the list is the preorder traversal of a binary search tree and no if it is not. Follow this format exactly: Case, one space, the case number, a colon, one space, and the answer for that case, with no trailing spaces.