Guitar Hero

In the 100% original game String Instrument Champion, the notes of a song are shown as points on the strings of a guitar. Notes are represented as integers, and the integer is the pitch of the note. No two notes are played at the same time in any String Instrument Champion song.

A song can contain far more notes than there are strings on the guitar. So we place the notes on the strings according to a set of rules. Sometimes this works out, but not always. When we place the notes on the strings, we have the following requirements:

• The first note may be on any string.
• If the previous note had a lower pitch than the next note, the next note must be on a higher string.
• If the previous note had a higher pitch than the next note, the next note must be on a lower string.
• If the previous note had the same pitch as the next note, the next note must be on the same string.

You are given a song with $n$ notes numbered from 1, and the guitar has $m$ strings. You are also given $q$ intervals in the song. An interval is represented by the integers $a$ and $b$, where the first note in the interval has index $a$ and the last note has index $b$.

For each interval we now ask: is it possible to place the notes contained in the interval on strings so that the requirements are met?

The first line contains three integers $n$, $m$, and $q$ ($1 \leq n, m, q \leq 10^5$). The second line contains $n$ integers $t_i$ ($1 \leq t_i \leq 10^9$). Then follow $q$ lines, each with two integers $a_i$ and $b_i$ ($1 \leq a_i \leq b_i \leq n$).

Print $q$ lines with "ja" or "nej", one for each interval. Print "ja" if it is possible to place the notes in the interval from $a_i$ to $b_i$ so that the requirements are met, otherwise "nej".