Truy vấn nhỏ nhất

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 (số nguyên không âm 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$.

Do bận tái cấu trúc và số truy vấn rất lớn, bác nông dân Đạt đành tìm đến bạn nhờ giúp đỡ.

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.

Dữ liệu vào

• 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$).

Dữ liệu ra

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$.

Ràng buộc

• $1\le n,q\le 5\times {10}^5$.
• $0\le a_i\le {10}^9$.
• $1\le l\le r\le n$.

Subtasks

• Subtask 1 ($24\%$ số điểm): $n,q\le 5\times {10}^3$.
• Subtask 2 ($48\%$ số điểm): $n,q\le 5\times {10}^4$.
• Subtask 3 ($28\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ