Học viện Siêu Năng Lực có ~N~ học viên, mỗi học viên có một chỉ số năng lực là một số nguyên trong khoảng từ 0 đến ~N~. Điểm yếu của một nhóm học viên có chỉ số từ ~L~ đến ~R~ là số nhỏ nhất còn thiếu trong đoạn ~[L, R]~. "Số nhỏ nhất còn thiếu" trong đoạn ~[L, R]~ là số nguyên nhỏ nhất từ 0 đến ~N~ mà không xuất hiện trong danh sách chỉ số năng lực của các học viên từ vị trí ~L~ đến ~R~.

Yêu cầu: Cho danh sách chỉ số năng lực của ~N~ học viên và ~Q~ truy vấn, mỗi truy vấn gồm 2 số ~L~ và ~R~. Hãy đưa ra điểm yếu của nhóm ~[L, R]~.

Input

• Dòng đầu tiên chứa hai số nguyên ~N~ và ~Q~ (~1 \le N, Q \le 10^5~) tương ứng với số lượng học viên và số truy vấn.
• Dòng thứ hai gồm ~N~ số nguyên tương ứng chỉ số năng lực của ~N~ học viên.
• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L, R~ (~1 \le L \le R \le N~), biểu thị một truy vấn.

Output

• Gồm ~Q~ dòng, dòng thứ ~i~ chứa đáp án của truy vấn thứ ~i~.