Thời gian gần đây, phong trào chạy việt dã phát triển nở rộ ở khắp các tỉnh thành trên toàn quốc. Năm nay, các vận động viên tập trung về tỉnh Hòa Bình tham gia giải chạy Hòa Bình Marathon. Để đảm bảo hỗ trợ tốt nhất cho các vận động viên tham gia giải, chủ nhà Hòa Bình đã bố trí ~N~ tình nguyện viên tại ~N~ vị trí trên đường chạy. Để đảm bảo các tình nguyện viên được sắp xếp một cách hợp lí, Ban tổ chức đưa ra ~Q~ câu hỏi, mỗi câu hỏi yêu cầu cho biết số tình nguyện viên trên đoạn đường cho trước.

Yêu cầu

Em hãy viết chương trình để trả lời các câu hỏi của ban tổ chức.

Dữ liệu đầu vào

Gồm ~Q + 2~ dòng:

• Dòng đầu chứa hai số nguyên dương ~N, Q~ ~(1 \le N \le 10^5;\ 1 \le Q \le 10^5)~.
• Dòng thứ hai chứa ~N~ số nguyên phân biệt ~x_1, x_2, ..., x_N~ là vị trí các tình nguyện viên ~(0 \le x_i \le 10^9;\ 1 \le i \le N)~.
• ~Q~ dòng tiếp theo mỗi dòng chứa hai số nguyên ~A~ và ~B~, ứng với mỗi câu hỏi của Ban tổ chức ~(0 \le A, B \le 10^9)~.

Dữ liệu đầu ra

Gồm ~Q~ dòng, mỗi dòng tương ứng với câu trả lời cho câu hỏi của Ban tổ chức.

Ràng buộc dữ liệu

• Subtask 1: Có 50% điểm số ứng với ~N \le 100;\ Q \le 1000~.
• Subtask 2: Có 50% điểm số ứng với các trường hợp còn lại.

Ví dụ

Ví dụ 1

INPUT

4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10

OUTPUT

2
2
3
4
1
0