Trên cánh đồng, bác John đặt ~n~ bố cỏ ở các vị trí khau nhau dọc trên con đường thẳng từ đầu đến cuối của cánh đồng. Để ước lượng sự phân bố số cỏ trên cánh đồng, bác hỏi Bessi ~m~ câu hỏi dạng:

Cho hai số A và B, Bessi cần trả lời cho bác biết có bao nhiêu bó cỏ nằm từ vị trí A đến vị trí B?

Input

• Dòng đầu tiên gồm hai số ~n, m (n, m \le 10^5)~ là số bó cở và số câu hỏi của bác John.
• Dòng tiếp theo chứa ~n~ số ~a_1, a_2, ..a_n~ là vị trí của ~n~ bó cỏ (~0 \le a_i \le 10^9)~
• ~m~ dòng tiếp theo, mỗi dòng gồm hai số A, B ~(0 \le A, B \le 10^9)~là một câu hỏi của bác John.

Output

~m~ số tương ứng là câu trả lời của ~m~ câu hỏi của bác John

Ví dụ

Sample Input

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

Sample Output

2
2
3
4
1
0