미래 세대의 번영과 평화를 위해 UN은 세계에서 가장 큰 사탕을 만들기로 했다.

그 재료는 산 꼭대기에서 철도로 가져와서 제네바 호수에 부어야 한다.

철도 시스템은 산아래의 호수로 가파르게 간다. 아래와 같이 중에 T모양의 분기가 있다.

지금 N개의 재료 각각이 자신의 철도차량이 있다. 이때 철도차량은 양수 1부터 n까지 할당되어 있다.

재료는 호수에 1,2,3,...,N순으로 부어져야 한다. 그러나 철도차량은 랜덤순서로 배치되어 있다.

특히 오늘 무거운 중량 때문에 어려움이 있다. 당신은 단지 철도차량을 호수로 보내거나, 분기(branch)로 보내거나 할 수 있다.

호수에 재료를 1,2,3,...,N 순서로 가져갈 수 있을 까?

예를 들어 차량의 순서가 2,3,1,4이면 우리는 아래의 순서대로 보낼 수 있다.

1. 4번 차량을 분기로 보내고

2. 1번 차량을 호수로 보내고

3. 3번 차량을 분기로 보내고

4. 2번 차량은 호수로 보내고

5. 분기에 있는 3번 차량을 호수로 보내고

6. 분기에 있는 4번 차량을 호수로 보내면 된다.

첫줄에 테스트할 수를 나타내는 정수 T가 입력된다.(1<=T<=10)

각 테스트는 재료를 실은 차량의 수를 나타내는 N이 입력된다(1<=N<=100,000)

다음 줄 부터 N줄에 걸쳐 차량의 순서가 입력된다.

(차량의 번호는 1~ N 중에 하나이며 중복은 없다)

각 테스트에서 순서대로 호수로 보낼 수 있다면

각 줄에 Y를 출력하고 아니면 N를 출력하라.

Simple Stacks