| 제네바 사탕 |
|---|
미래 세대의 평화와 번영을 UN에서는 세계에서 가장 큰 사탕을 만들고 있다. 사탕의 제조방법은 독특하게도 열차를 이용해서 산 꼭대기에서 제네바호(유럽에서 가장 큰 호수)로 사탕의 원료를 쏟아 붓는 방식이다. 철도는 산꼭대기에서 호수로 가파르게 설치되어 있으며, 다음의 그림처럼 중간에 T자 형태의 샛길이 나 있다.
지금 N개의 원료들이 열차에 실려 있다. 각각의 열차에는 1부터 N까지의 양의 정수로 번호가 매겨져 있다. 그런데 사탕 원료는 호수로 1, 2, 3,..., N 순으로 번호 순서대로 쏟아 부어야 하지만 열차들은 현재 무작위 순서로 내려오고 있다, 열차는 오로지 호수로 내려가거나 샛길로 갈 수 있다. 과연 호수로 원료를 1, 2, 3, ..., N 순으로 쏟아부을 수 있을까? 산꼭대기에서 내려오는 열차 번호가 주어질 때, 1, 2, 3, ... , N 순서대로 호수로 내려갈 수 있는지 확인하는 프로그램을 작성하시오. 예를 들어 열차의 순서가 2, 3, 1, 4 순서로 내려온다면, 다음과 같은 방식으로 열차의 순서를 재조정할 수 있다.
4번 열차를 샛길로 빼낸다. |
| 입력 | |
|---|---|
| 첫 번째 줄에는 사탕 종류의 개수를 나타내는 T(1<=T<=10)가 주어진다. 그 다음 줄에는 한 종류의 사탕을 만들기 위한 원재료의 수 N(1<=N<=100,000)와 N개의 줄에 걸쳐 산꼭대기에서 내려오는 열차번호가 주어진다. 열차번호는 항상 1부터 N사이의 정수다. | |
| 출력 | |
|---|---|
입력으로 받은 각각의 사탕 종류에 대해 열차가 1, 2, 3, .., N순서대로 호수에 도달 가능하면 Y를, 그렇지 않으면 N을 출력한다. 예시1 : 입력으로 2가지 종류의 사탕을 만들기 위한 원재료 순서가 주어진다. 첫 번째 사탕을 만들기 위해서는 4개의 원재료가 필요한데, 현재 산꼭대기에서 4,1,3,2 순서로 내려오고 있다. 그대로 내려온다면, 호수에 4,1,3,2 순서로 도착하게 된다. 두 번째 사탕을 만들기 위해서 역기 4개의 원재료가 필요하며 현재 산꼭대기에서 2,3,1,4 순서로 내려오고 있다. 샛길로 빠지지 않고 그대로 내려온다면 호수에 2,3,1,4 순서로 도착하게 된다. | |
| 예시 | |||
|---|---|---|---|
| 1 | 입력 | 2 4 2 3 1 4 4 4 1 3 2 | |
| 출력 | Y N | ||