Lớp học của Purple có ~n~ học sinh , mỗi học sinh có 'khả năng' bí ẩn là một số tự nhiên có giá trị trong khoảng từ 0 đến ~n~.

Gọi "đặc điểm" của đoạn ~(l , r)~ là : 'khả năng' bé nhất còn thiếu của các học sinh trong đoạn từ ~l~ đến ~r~ .

Để kiểm tra năng lực của giáo viên cũng như độ quan tâm của thầy giáo với học sinh của mình , thầy hiệu trưởng đã ra ~q~ câu hỏi có dạng ~(l , r)~ yêu cầu thầy giáo phải trả lời được "đặc điểm" của từng dãy học sinh trong đoạn tương ứng.

Input

• Dòng đầu tiên là số nguyên dương ~n~ là số học sinh và ~q~ là số câu hỏi của thầy hiệu trưởng
• ~n~ số nguyên dương tiếp theo là khả năng của học sinh thứ ~i~
• ~q~ dòng tiếp theo là 2 giá trị ~(l,r)~ .

Output

In ra ~q~ dòng là kết quả của bài toán

Sample Input

5 2 
0 2 3 4 5 
1 3 
2 4

Sample Output

1
0

Giới Hạn

• 30% test có ~n,q \le 10^2~
• 40% test có ~n,q \le 5000~
• 30% test còn lại có ~n,q \le 10^5~