Cuộc thi chạy việt dã năm nay có nhiều vận động viên từ khắp nơi về tham dự. Để đảm bảo các vận động viên không bị lạc đường cũng như có sự hỗ trợ khi cần, ban tổ chức đã sắp xếp N tình nguyện viên tại các điểm khác nhau dọc con đường chạy thi. Để đảm bảo rằng các tình nguyện viên được sắp xếp cách nhau 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 trong một đoạn đường cho trước.

Dữ liệu vào:

+ Dòng đầu chứa 2 số \(n\) và \(q\). \((1\ \leq \ n\ \leq \ 10^{5}\ ,1\ \leq \ q\ \leq \ 10^{5})\)

+ Dòng thứ 2 chứa \(n\) số nguyên phân biệt: \(x1,\ x2,\ \ldots,xN\), mỗi số thuộc đoạn \(0\ldots 10^{9}\) cho biết vị trí một tình nguyện viên.

+ Mỗi dòng trong \(q\) dòng sau chứa 2 số nguyên \(a\) và \(b\ (0\ \leq \ a\ \leq \ b\ \leq \ 10^{9})\) ứng với câu hỏi cho biết có bao nhiêu tình nguyện viên trong đoạn từ \(a\) đến \(b\).

Kết ủa:

Đưa ra \(q\) dòng, mỗi dòng là một số nguyên trả lời cho câu hỏi tương ứng

Ví dụ:

Giới hạn:

• Có 50% số điểm tương ứng với \(n\ \leq \ 10^{2},\ \ q \leq 10^{3},\ 0 \leq a \leq b \leq 10^{2},\ 0 \leq \ xi\ \leq 10^{5}\);

• Có 50% số điểm tương ứng với các trường hợp còn lại;