Preorder Traversals

Interview

Time limit1sMemory limit256 MB

Summary

Decide whether each given number list is the preorder traversal of some binary search tree.

Level: Medium5 of 10
Topics: Stack, Tree
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples2

Example 1

Input

2 3 1 -7
50 30 20 10 25 40 45
70 90 80 -1

Expected output

Case 1: no
Case 2: yes

Example 2
Input
```
1 -1
```
Expected output
```
Case 1: yes
```