문제
모그는 들여쓰기와 번호를 사용해 공책에 배운 내용을 정리한다. 공책의 내용은 $N$개의 줄로 구성되어 있고, 각 줄은 적절한 들여쓰기와 함께 번호가 매겨져 있다.
들여쓰기는 아래 규칙을 따른다.
- 첫 번째 줄은 $0$칸 들여쓰기한다.
- 각 줄은 직전 줄보다 최대 한 칸 많이 들여쓰기할 수 있으며 그보다 적은 칸만큼 들여쓰기할 수도 있다.
번호는 아래 규칙을 따른다.
- 같은 칸만큼 들여쓰기한 줄들은 $1$부터 $1$씩 커지는 번호를 매긴다.
- 단, 같은 칸만큼 들여쓰기한 가장 가까운 이전 줄이 있고 그 줄과 현재 줄 사이에 더 적게 들여쓰기한 줄이 있다면, 현재 줄에는 번호 $1$을 매긴다.
길이 $N$의 정수 수열 $A_1, A_2, \cdots, A_N$이 주어질 때, $i$번 줄의 번호로 $A_i$가 매겨지도록 적절히 들여쓰기할 수 있는지 판단하자.
입력
첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1\le T\le 100\ 000)$
각 테스트 케이스의 첫째 줄에 양의 정수 $N$이 주어진다. $(1\le N\le 100\ 000)$
각 테스트 케이스의 둘째 줄에 양의 정수 $A_1, A_2,\cdots, A_N$이 공백으로 구분되어 주어진다. $(1\le A_i\le N)$
모든 테스트 케이스에서 $N$의 합은 $1\ 000\ 000$을 넘지 않는다.
출력
각 테스트 케이스의 첫째 줄에, 해당 수열이 모그의 규칙을 만족하는 들여쓰기로부터 만들어질 수 있다면 YES, 만들어질 수 없다면 NO를 출력한다.
예제 입력 1
2 3 1 1 1 4 1 2 3 3
예제 출력 1
YES NO
출처
Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2026. 01-02. D번
- 문제를 만든 사람: lunarlity
- 문제를 검수한 사람: chogahui05, jthis, utilforever