Sau vòng loại trực tuyến của một cuộc thi lập trình, hệ thống chấm ghi nhận điểm của ~n~ thí sinh; thí sinh thứ ~i~ đạt ~a_i~ điểm (điểm được cộng dồn qua nhiều bài và có thưởng theo thời gian nộp nên có thể rất lớn).

Ban tổ chức đang cân nhắc các mức điểm để phân hạng giải thưởng. Họ đưa ra ~q~ phương án, phương án thứ ~j~ là một khoảng điểm từ ~lo_j~ đến ~hi_j~, và muốn biết có bao nhiêu thí sinh rơi vào khoảng đó.

Yêu cầu

Với mỗi phương án ~(lo_j, hi_j)~, hãy đếm số thí sinh ~i~ thoả mãn ~lo_j \le a_i \le hi_j~ (tính cả thí sinh đạt đúng ~lo_j~ điểm hoặc đúng ~hi_j~ điểm).

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~q~;
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~, các số cách nhau bởi dấu cách;
• ~q~ dòng tiếp theo, dòng thứ ~j~ chứa hai số nguyên ~lo_j~ và ~hi_j~.

Kết quả ra

Ghi ra ~q~ dòng, dòng thứ ~j~ ghi một số nguyên là câu trả lời cho phương án thứ ~j~.

Ràng buộc

~1 \le n, q \le 2 \cdot 10^5~; ~0 \le a_i \le 10^9~; ~0 \le lo_j \le hi_j \le 10^9~.

• Subtask 1 (30% số điểm – test 01–06): ~n, q \le 2000~;
• Subtask 2 (20% số điểm – test 07–10): ~a_i \le 10^5~ và ~hi_j \le 10^5~ với mọi truy vấn;
• Subtask 3 (50% số điểm – test 11–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

6 5
70 55 90 70 30 85
60 80
0 100
91 100
70 70
30 85

Kết quả ra mẫu 1

2
6
0
2
5

Giải thích

Khoảng ~[60, 80]~ chứa hai thí sinh cùng đạt ~70~ điểm; khoảng ~[0, 100]~ chứa cả ~6~ thí sinh; không có thí sinh nào đạt từ ~91~ đến ~100~ điểm; khoảng ~[70, 70]~ chứa hai thí sinh đạt đúng ~70~ điểm; khoảng ~[30, 85]~ chứa mọi thí sinh trừ thí sinh đạt ~90~ điểm (thí sinh đạt đúng ~30~ điểm và đúng ~85~ điểm đều được tính).