기타 히어로

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

한 곡에는 기타 줄의 개수보다 훨씬 많은 음이 들어 있을 수 있다. 따라서 우리는 정해진 규칙에 따라 음을 줄에 배치한다. 때로는 잘 되지만, 항상 그렇지는 않다. 음을 줄에 배치할 때 우리는 다음 조건을 만족해야 한다:

• 첫 번째 음은 어떤 줄에 있어도 된다.
• 직전 음의 높이가 다음 음보다 낮았다면, 다음 음은 더 높은 줄에 있어야 한다.
• 직전 음의 높이가 다음 음보다 높았다면, 다음 음은 더 낮은 줄에 있어야 한다.
• 직전 음의 높이가 다음 음과 같았다면, 다음 음은 같은 줄에 있어야 한다.

$n$개의 음이 1부터 번호가 매겨진 곡이 주어지고, 기타에는 $m$개의 줄이 있다. 또한 곡의 $q$개의 구간이 주어진다. 구간은 정수 $a$와 $b$로 표현되며, 구간의 첫 번째 음은 번호 $a$, 마지막 음은 번호 $b$이다.

이제 각 구간에 대해 묻는다: 구간에 포함된 음들을 조건을 만족하도록 줄에 배치하는 것이 가능한가?

첫째 줄에는 세 정수 $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$).

$q$개의 줄에 "ja" 또는 "nej"를 하나씩 출력한다. 구간 $a_i$부터 $b_i$까지의 음을 조건을 만족하도록 배치할 수 있으면 "ja"를, 그렇지 않으면 "nej"를 출력한다.