Guitar Hero

PO 심사위원단의 100% 독창적인 게임 String Instrument Champion에서는 노래의 음표가 기타 줄 위의 점으로 표시된다. 음표는 정수로 표현되며, 그 정수는 음표의 음높이를 나타낸다. String Instrument Champion의 어떤 노래에서도 두 음표가 동시에 연주되지 않는다.

한 노래에는 기타의 줄 수보다 훨씬 많은 음표가 포함될 수 있다. 따라서 특정한 규칙 집합에 따라 음표를 줄에 배치한다. 때로는 가능하지만 항상 가능한 것은 아니다. 음표를 줄에 배치할 때 다음 요구 사항을 만족해야 한다.

• 첫 음표는 어느 줄에든 놓을 수 있다.

• 가장 최근 음표의 음높이가 다음 음표보다 낮다면, 다음 음표는 더 높은 줄에 놓여야 한다.

• 가장 최근 음표의 음높이가 다음 음표보다 높다면, 다음 음표는 더 낮은 줄에 놓여야 한다.

• 가장 최근 음표의 음높이가 다음 음표와 같다면, 다음 음표는 같은 줄에 놓여야 한다.

1부터 인덱스가 매겨진 $n$개의 음으로 이루어진 노래가 주어지고, 기타에는 $m$개의 줄이 있다. 또한 노래에서 $q$개의 구간이 주어진다. 구간은 정수 $a$와 $b$로 표현되며, 구간의 첫 음표는 인덱스 $a$이고 마지막 음표는 인덱스 $b$이다.

이제 각 구간에 대해 묻는다. 구간에 포함된 음표를 요구 사항을 만족하도록 줄에 배치할 수 있는가?

점수

당신의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 점수 | 제한

$1$ | $25$ | $n,m,q \le 50$

$2$ | $25$ | $n,m,q \le 5000$

$3$ | $25$ | $m \le 5$

$4$ | $25$ | 추가 제한 없음

첫째 줄에 세 정수 $n$, $m$, 그리고 $q$가 주어진다 ($1 \leq n, m, q \leq 10^5$). 둘째 줄에 $n$개의 정수 $t_i$가 주어진다 ($1 \leq t_i \leq 10^9$). 그다음 $q$개의 줄에 각각 두 정수 $a_i$와 $b_i$가 주어진다 ($1 \leq a_i \leq b_i \leq n$).

각 구간마다 하나씩, "ja" 또는 "nej"를 담은 $q$개의 줄을 출력한다. 구간 $a_i$부터 $b_i$까지의 음표를 요구 사항을 만족하도록 배치할 수 있다면 해당 줄에 "ja"를 출력하고, 그렇지 않으면 "nej"를 출력한다.

예제 테스트 케이스 $1$에서는 줄이 세 개뿐이므로 수열 $1, 2, 2, 3, 4$을 표현하는 것이 불가능하다. 따라서 첫째 구간과 둘째 구간의 답은 nej가 된다. 반면 나머지 구간은 줄에 배정할 수 있다. 예를 들어 구간 $(1, 5)$의 음표를 줄 $2, 1, 2, 2, 3$에 배정할 수 있다.

예제 테스트 케이스 $2$에서는 요구 사항을 만족하는 음표의 줄 배정이 하나뿐이다: $1, 2, 3, 1, 2, 3$.