Đối thủ cân sức - Tra cứu theo khoảng Elo

Câu lạc bộ cờ vua có n kỳ thủ. Kỳ thủ thứ i có điểm xếp hạng Elo là a_i; các kỳ thủ có thể có Elo bằng nhau.

Yêu cầu

Có q câu hỏi, mỗi câu hỏi gồm hai số L và R. Hãy cho biết có bao nhiêu kỳ thủ có Elo nằm trong đoạn [L, R], tức là L ≤ a_i ≤ R.

Input

• Dòng đầu chứa hai số nguyên n và q.
• Dòng thứ hai chứa n số nguyên a_1, a_2, ..., a_n.
• q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R của một câu hỏi.

Output

In q dòng. Dòng thứ j là số kỳ thủ có Elo nằm trong đoạn của câu hỏi thứ j.

Ràng buộc

• 1 ≤ n, q ≤ 100000.
• 1 ≤ a_i ≤ 10^9.
• 1 ≤ L ≤ R ≤ 10^9.

Nhóm test

• Test 01-05 (50 điểm): n, q ≤ 1000.
• Test 06-10 (50 điểm): ràng buộc đầy đủ.

Ví dụ 1

Input

7 4
1500 1200 1800 1500 1350 2000 1650
1300 1600
1500 1500
2100 2500
1000 2000

Output

3
2
0
7

Giải thích

Đoạn [1300, 1600] chứa 1350, 1500, 1500 nên có 3 kỳ thủ. Đoạn [1500, 1500] có 2 kỳ thủ. Không ai nằm trong [2100, 2500]; cả 7 kỳ thủ nằm trong [1000, 2000].