자동차 경주

시간 제한1초메모리 제한128 MB

요약

차들이 도착한 순서가 주어질 때, 단일 선입선출 우회로로 1부터 N까지 오름차순 정렬이 가능한지 판정한다.

난이도: 쉬움10점 중 3점
유형: 스택, 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

아래 그림과 같은 트랙에서 자동차 경주가 열린다.

트랙 그림

출발선으로 이어지는 길은 하나뿐이므로, 자동차들은 예선 성적에 따라 부여받은 번호 순서대로, 즉 $1, 2, \dots, N$ 순으로 출발선에 늘어서야 한다. 자동차들은 어떤 순서로 정문에 도착하는데, 한 줄짜리 우회로 하나를 이용해 이 자동차들을 $1, 2, \dots, N$ 순서로 다시 세울 수 있는지 판단하려고 한다.

모든 자동차는 화살표 방향으로 앞으로만 움직일 수 있다. 정문에 도착한 자동차는 곧장 출발선으로 가거나, 우회로로 들어가 대기할 수 있다. 우회로는 한 줄이고 자동차는 뒤로 갈 수 없으므로, 우회로에 먼저 들어간 자동차가 먼저 나온다(선입선출). 우회로는 경주에 참가한 모든 자동차를 담을 수 있을 만큼 충분히 길다고 가정한다.

예를 들어 자동차 네 대가 $1, 3, 2, 4$ 순서로 도착했다고 하자. 이때 다음과 같이 $1, 2, 3, 4$ 순서로 세울 수 있다. 먼저 $1$ 번이 곧장 출발선으로 간다. $3$ 번은 우회로로 들어가 대기한다. $2$ 번이 곧장 출발선으로 간다. 이어서 $3$ 번이 우회로에서 나와 출발선에 도착한다. 마지막으로 $4$ 번이 곧장 출발선으로 간다.

도착 순서가 주어질 때, 자동차들을 $1, 2, \dots, N$ 순서로 세울 수 있는지 판정하여라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 경주에 참가하는 자동차의 수 $N$ ( $1 \le N < 100$ )이 주어진다. 둘째 줄에는 자동차가 정문에 도착하는 순서, 즉 $1, 2, \dots, N$ 의 순열이 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 한 줄에, 자동차들을 $1, 2, \dots, N$ 순서로 세울 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제5

예제 1
입력
```
2
4
1 3 2 4
3
3 2 1
```
예상 출력
```
YES
NO
```
예제 2
입력
```
1
1
1
```
예상 출력
```
YES
```
예제 3
입력
```
1
6
1 2 3 4 5 6
```
예상 출력
```
YES
```
예제 4
입력
```
2
2
2 1
3
1 2 3
```
예상 출력
```
YES
YES
```

예제 5

입력

예상 출력

YES
NO
YES
NO
YES
NO