이진 탐색 트리의 전위 순회

이진 탐색 트리는 모든 노드에서 왼쪽 서브트리의 값이 전부 그 노드의 값보다 작고, 오른쪽 서브트리의 값이 전부 그 노드의 값보다 크며, 모든 서브트리도 다시 이진 탐색 트리인 트리다. 빈 트리는 이 문제에서 다루지 않는다. 노드에는 순서가 정의된 아무 자료형이나 담을 수 있지만, 여기서는 1,000,000,000보다 작은 양의 정수만 다룬다.

전위 순회는 다음 의사코드로 정의한다.

preorder_traversal(root)
    root의 값을 출력한다
    root에 왼쪽 서브트리가 있으면
        preorder_traversal(root의 왼쪽 서브트리)
    root에 오른쪽 서브트리가 있으면
        preorder_traversal(root의 오른쪽 서브트리)

예를 들어 50, 30, 20, 10, 25, 40, 45, 70, 90, 80은 어떤 이진 탐색 트리의 전위 순회 결과다. 반면 2, 3, 1은 어떤 이진 탐색 트리의 전위 순회 결과도 아니다. 가장 먼저 출력된 2가 루트여야 하는데, 3은 2보다 크므로 오른쪽 서브트리에 들어가고 뒤이어 나온 1은 2보다 작으므로 왼쪽 서브트리에 들어가야 한다. 전위 순회는 왼쪽 서브트리를 오른쪽 서브트리보다 먼저 출력하므로 1이 3보다 뒤에 올 수 없다.

왼쪽은 작고 오른쪽은 크다는 조건이 등호를 허용하지 않으므로, 같은 값이 두 번 이상 나오는 목록은 어떤 이진 탐색 트리의 전위 순회 결과도 아니다.

수의 목록을 읽어 이 목록이 어떤 이진 탐색 트리의 전위 순회 결과인지 판정한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 양의 정수 목록과 목록의 끝을 알리는 음의 정수 하나로 이루어지고, 이 음의 정수는 목록에 포함하지 않는다. 긴 목록은 여러 줄에 걸쳐 주어질 수 있다. 수 사이의 공백과 줄바꿈은 형식이 정해져 있지 않으므로 공백으로 구분된 정수만 가정한다. 목록에 들어 있는 수의 개수는 1 이상 1,000 이하다. 입력은 파일의 끝까지 처리한다.

각 케이스마다 목록이 어떤 이진 탐색 트리의 전위 순회 결과이면 yes를, 아니면 no를 출력한다. 형식은 정확히 다음과 같다. Case, 공백 한 칸, 케이스 번호, 콜론, 공백 한 칸, 그 케이스의 답. 줄 끝에 공백을 남기지 않는다.