Chụp ảnh

Tại một học viện đào tạo kỹ năng sống, có một lớp học đặc biệt gồm \(K\) học viên, mỗi học viên được đánh số từ \(1\) đến \(K\). Trong lớp học này, mỗi học viên có chiều cao khác nhau, không ai trùng chiều cao với ai.

Vào cuối khóa, cô giáo Linh quyết định tổ chức một buổi chụp ảnh kỷ niệm. Cô đã chuẩn bị một danh sách \(A_1, A_2, \dots, A_N\) biểu thị thứ tự các học viên trong bức ảnh từ trái sang phải. Điều đặc biệt là một học viên có thể xuất hiện nhiều lần trong danh sách \(A\), do cô muốn các học viên xuất hiện nhiều lần ở các vị trí khác nhau.

Cô Linh rất yêu thích sự cân đối, nên cô muốn kiểm tra xem liệu các học viên trong một đoạn bất kỳ của danh sách có thể sắp xếp thành một trình tự chiều cao "xuống - lên" thú vị hay không. Một trình tự được gọi là "xuống - lên" nếu chiều cao của các học viên trong đoạn đó thỏa mãn điều kiện:

• \(h[A_x] > h[A_{x+1}] < h[A_{x+2}] > h[A_{x+3}] < \dots h[A_y]\),

  với \(h[i]\) là chiều cao của học viên \(i\).

\begincenter

\endcenter

Cô Linh có \(Q\) câu hỏi, mỗi câu hỏi yêu cầu kiểm tra một đoạn \([x, y]\) trong danh sách \(A\). Hãy giúp cô trả lời mỗi câu hỏi: liệu có dãy chiều cao nào có thể thỏa mãn "xuống - lên" hay không.

Input

• Dòng đầu tiên chứa ba số nguyên \(N, K, Q\) \((1 \leq N, K \leq 3 \times 10^3, 1 \leq Q \leq 10^6)\): độ dài của danh sách, số lượng học viên và số lượng câu hỏi.
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \dots, A_N\) \((1 \leq A_i \leq K)\): danh sách học viên.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) \((1 \leq x <= y \leq N)\), biểu thị đoạn cần kiểm tra.

Output

• Với mỗi câu hỏi, in ra YES nếu đoạn \([x, y]\) có thể sắp xếp thành trình tự "xuống - lên", ngược lại in ra NO.

Example

6 3 3
1 1 2 3 1 2
1 2
2 5
2 6

NO
YES
NO

Scoring

• Có 16% số điểm: \(2 \leq N \leq 3000\), \(K = 2\), \(1 \leq Q \leq 10^6\).
• Có 24% số điểm: \(2 \leq N \leq 500\), \(2 \leq K \leq \min(N, 5)\), \(1 \leq Q \leq 10^6\).
• Có 28% số điểm: \(2 \leq N \leq 3000\), \(2 \leq K \leq N\), \(1 \leq Q \leq 2000\).
• 32% số điểm còn lại: \(2 \leq N \leq 3000\), \(2 \leq K \leq N\), \(1 \leq Q \leq 10^6\).