철도역

시간 제한10초메모리 제한512 MB

요약
1번부터 N번까지 순서대로 들어오는 객차를 외톨이 선로 하나로 목표 순열 순서대로 내보낼 수 있는지 판정한다.
난이도

보통10점 중 4점

유형
스택, 시뮬레이션
정답자
아직 제출이 없습니다

문제

어느 산악 국가에 유명한 철도역이 있다. 이 역은 수십 년 전 자금이 매우 부족하던 시절에 지어져서 지상 선로 하나만 놓을 수 있었다. 게다가 역은 막다른 형태(그림 참고)로만 지을 수 있었고, 공간이 부족해 선로도 하나뿐이다.

이 지역에는 방향 AA에서 들어온 열차가 객차의 순서를 어떤 식으로든 재편성한 뒤 방향 BB로 떠나는 전통이 있다. 방향 AA에서 들어오는 열차에는 객차가 NN개(N≤1000N \le 1000) 있고, 객차에는 들어오는 순서대로 1,2,…,N1, 2, \ldots, N의 번호가 붙어 있다. 열차 편성 책임자는 방향 BB로 떠나는 객차의 순서를 a1,a2,…,aNa_1, a_2, \ldots, a_N으로 만들 수 있는지 알아야 한다.

요구한 객차 순서를 만들 수 있는지 판단하는 프로그램을 작성하여 책임자를 도와주자. 객차는 역에 들어가기 전에 한 량씩 떼어 낼 수 있고, 방향 BB 선로에 도착할 때까지 스스로 움직일 수 있다고 가정한다. 또한 역에는 언제든 필요한 만큼 많은 객차가 머무를 수 있다. 하지만 한 번 역에 들어간 객차는 방향 AA 선로로 돌아갈 수 없고, 한 번 역을 떠나 방향 BB로 나간 객차는 다시 역으로 돌아올 수 없다.

입력

입력은 여러 블록으로 이루어진다. 마지막 블록을 제외한 각 블록은 열차 하나와 그 열차에 대한 하나 이상의 재편성 요구를 나타낸다.

블록의 첫 줄에는 위에서 설명한 정수 NN이 주어진다. 블록의 다음 줄부터는 한 줄에 하나씩 1,2,…,N1, 2, \ldots, N의 순열이 주어진다. 블록의 마지막 줄에는 00 하나만 있다.

마지막 블록은 00 하나만 있는 한 줄이다.

출력

입력에서 순열이 주어진 줄마다 출력 한 줄을 차례로 출력한다. 해당 줄에서 요구한 순서로 객차를 편성할 수 있으면 Yes를, 그렇지 않으면 No를 출력한다.

입력의 블록 하나에 해당하는 줄을 모두 출력한 뒤에는 빈 줄 하나를 출력한다. 입력의 마지막 블록(0 하나만 있는 블록)에 해당하는 출력은 없다.

예제1

  1. 예제 1

    입력
    5
    1 2 3 4 5
    5 4 1 2 3
    0
    6
    6 5 4 3 2 1
    0
    0
    
    예상 출력
    Yes
    No
    
    Yes