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.

Input

Dữ liệu vào từ tệp CuocThi.Inp:

• Dòng đầu chứa 2 số ~N~ và ~Q~ ~(1 \le N \le 10^5, 1 \le Q \le 10^5)~.
• Dòng thứ 2 chứa ~N~ số nguyên phân biệt: ~x_1, x_2, \ldots, x_N~, mỗi số thuộc đoạn ~[0, 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 \le A \le B \le 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~.

Output

Kết quả ghi ra tệp CuocThi.Out:

• Đư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ụ

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

Giới hạn

• ~1 \le N \le 10^5~, ~1 \le Q \le 10^5~, ~0 \le x_i \le 10^9~, ~0 \le A \le B \le 10^9~.
• Có 50% số điểm tương ứng với ~N \le 10^2~, ~Q \le 10^3~, ~0 \le A \le B \le 10^2~, ~0 \le x_i \le 10^5~.
• Có 50% số điểm tương ứng với các trường hợp còn lại.