Trong lúc train về thuật toán DP, vì quá mệt mỏi Khang và Khôi đã cùng nhau nghĩ ra và rủ Kiệt chơi một trò chơi đối kháng để giải trí.

Để làm khó được Kiệt, Khang sẽ phải tự suy nghĩ sinh ra một dãy số gồm ~N~ chữ số và ~Q~ truy vấn. Với mỗi truy vấn sẽ gồm ~2~ số ~L~ và ~R~, yêu cầu hãy tìm số ~M~ lớn nhất có thể thỏa mãn:

• Gọi ~C_1, C_2,... C_M~ là ~M~ phần tử được chọn trong đoạn từ ~L~ đến ~R~.
• Tất cả ~C_i~ đều lớn hoặc bằng ~M~.

Nếu Kiệt có thể trả lời ~Q~ truy vấn hóc búa của Khang trong ~2~ giây thì Kiệt sẽ thắng. Thế nhưng Kiệt đang rất đau đầu về các bài toán DP đang train, nên bạn hãy thay Kiệt chơi trò chơi này nhé.!

Input

Dòng đầu tiên chứa số nguyên ~N~ và ~Q~.

Dòng tiếp theo chứa ~N~ số nguyên ~A_1, A_2, ... A_N~ ~(1 \leq A_i \leq 2 * 10^5)~ là dãy số mà Khang đã sinh ra.

~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ tương ứng với truy vấn mà Khang sẽ hỏi Kiệt.

Output

In ra ~Q~ dòng, mỗi dòng là câu trả lời cho truy vấn tương ứng.

Sample Input

7 4
1 1 1 3 20 4 2
3 4
3 7
3 6
1 7

Sample Output

1
3
3
3

Ràng buộc:

• Subtask 1: 20% số test ứng với ~N, Q \leq 10^3~.
• Subtask 2: 30% số test ứng với ~N, Q \leq 5 * 10^4~.
• Subtask 2: 50% số test ứng với ~N, Q \leq 2 * 10^5~.