Bác nông dân Đạt có ~n~ con bò. Để quản lí đàn bò của mình cho tốt, mỗi con bò được đánh số bằng một số nguyên không âm, con bò thứ ~i~ có số là ~a_i~ biểu diễn chủng tộc của con bò đó. Các chú bò sinh sống với nhau rất tốt, tuy nhiên để tái cơ cấu cấu trúc đàn bò, bắt buộc bác nông dân Đạt phải thực hiện một vài phép toán để tính toán độ tối ưu.

Cụ thể hơn, bác nông dân Đạt có ~q~ câu hỏi, mỗi câu hỏi là hai số nguyên ~l, r~ (~l \le r~), bác muốn biết chủng tộc nhỏ nhất không xuất hiện trong dãy (~a_l, a_{l+1}, \dots, a_r~). Ví dụ, với ~a = [3, 1, 0, 5, 3, 2, 6]~ và ~l = 1, r = 7~ thì câu trả lời sẽ là 4.

Yêu cầu: Với mỗi câu hỏi, hãy tìm chủng tộc nhỏ nhất không xuất hiện trong đoạn đã cho.

Input

• Dòng thứ nhất chứa hai số nguyên ~n, q~ (~1 \le n, q \le 5 \times 10^5~).
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ (~0 \le a_i \le 10^9~).
• Mỗi dòng trong số ~q~ dòng tiếp theo chứa hai số nguyên ~l, r~ - biểu diễn một câu hỏi (~1 \le l \le r \le n~).

Output

• Gồm ~q~ dòng, dòng thứ ~i~ chứa một số nguyên duy nhất là kết quả cho câu hỏi thứ ~i~.

Sample Input 1

7 4
3 1 0 5 3 2 6
1 7
1 3
4 7
2 3

Sample Output 1

4
2
0
2