Cho mảng \(A\) gồm \(N\) số nguyên dương. Từ một vị trí \(i\) (1-indexed), khi thực hiện một "nhảy", bạn sẽ nhảy tới vị trí \(j > i\) đầu tiên thỏa mãn \(A[j] > A[i]\). Nếu không có vị trí nào thỏa mãn, bạn sẽ nhảy ra ngoài mảng (coi như dừng lại ở trạng thái không hợp lệ).

Bạn cần xử lý \(Q\) truy vấn: Xuất phát từ vị trí \(U\), sau khi thực hiện đúng \(K\) lần nhảy liên tiếp, bạn đang ở vị trí nào? (Nếu nhảy ra ngoài mảng trước hoặc đúng lần thứ \(K\), in ra -1).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^5\)).
• Dòng hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(U\) và \(K\) (\(1 \le U \le N\), \(1 \le K \le 10^5\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra chỉ số vị trí đích (1-indexed) hoặc -1 nếu nhảy ra ngoài mảng.

Ràng buộc & Subtasks

• Subtask 1 (30% số điểm): \(N, Q \le 1000, K \le 1000\).
• Subtask 2 (70% số điểm): \(N, Q \le 10^5, K \le 10^5\).

Ví dụ

Input:

6 3
1 5 3 4 8 2
1 2
3 1
4 2

Output:

5
4
-1

Giải thích:

• Mảng: \([1, 5, 3, 4, 8, 2]\).
• Từ 1 (giá trị 1): nhảy 1 là tới 2 (giá trị 5). Từ 2 (giá trị 5): nhảy 2 là tới 5 (giá trị 8). \(\to\) Sau 2 nhảy từ 1: tới vị trí 5 (giá trị 8).
• Từ 3 (giá trị 3): nhảy 1 là tới 4 (giá trị 4).
• Từ 4 (giá trị 4): nhảy 1 là tới 5 (giá trị 8). Từ 5 (giá trị 8): không có phần tử nào lớn hơn phía sau \(\to\) nhảy ra ngoài \(\to\) kết quả -1.