Informatica Online Judge

  제네바 조약 사탕 [1085 / 043D]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 23   Total Tried : 32


The Champion of this Problem (C++) : gs15120 - 0ms / 1476byte
My Best Submission (C++) : N/A

[CCC2014S]

Background

미래의 국제 평화와 안녕을 위해, UN은 세상에서 가장 큰 사탕을 만들려고 한다.

사탕을 만들기 위한 재료는 제네바의 산꼭대기에서 아래쪽 제네바 호수까지 연결된 철도를 따라 이동되어야 하는데, 산꼭대기에서 호수까지 가파른 경사의 철도로 연결되어있으며, 중간에 아래와 같이 T자 모양의 갈림길이 있다.



N개의 재료가 1부터 N까지의 번호를 가지는 철도 차량에 실려 있을 때, 아래쪽 호수에는 1,2,3,...,N의 순서로 도착해야하지만, 철도 차량의 순서는 무작위적으로 섞여 있다.

차량은 위에서 아래로 이동시키거나, 오른쪽 T자 갈림길로만 넣었다 뺄 수 있을 때, 아래쪽 호수에 순서대로(1,2,3,...,N) 도착하게 만들 수 있을까?

예를 들어 산꼭대기의 철도 차량이 2,3,1,4의 순서로 위에서 아래로 서 있다면, 아래와 같은 방법으로 순서대로 이동 시킬 수 있게 된다.

- 4번 차량을 T 갈림길에 넣는다.
- 1번 차량을 호수로 보낸다.
- 3번 차량을 T 갈림길에 넣는다.
- 2번 차량을 호수로 보낸다.
- 3번 차량을 T 갈림길에서 꺼내 호수로 보낸다.
- 4번 차량을 T 갈림길에서 꺼내 호수로 보낸다.

Input

첫 번째 줄에는 확인할 테스트의 개수(T: 1<=T<=10)가 주어진다.

다음 줄부터 각 테스트 케이스가 입력되는데, 첫 줄에는 철도 차량의 개수(N: 1<=N<=100000)가 주어지고 그 다음에는 차량의 번호(1~N)가 위에서 아래로 순서대로 주어진다.

Output

각각의 테스트에 대해서 순서대로 호수로 보내기가 가능하면 Y, 그렇지 않으면 N을 출력한다.

IO Example

입력 예시
2
4
2
3
1
4
4
4
1
3
2


출력 예시
Y
N

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]