Per có ~n~ tấm thẻ, tấm thẻ thứ ~i~ ghi số nguyên ~A_i~. Nhiều tấm thẻ có thể ghi cùng một số.

Cho ~q~ truy vấn, mỗi truy vấn gồm hai số nguyên ~l~ và ~r~. Với mỗi truy vấn, hãy đếm số tấm thẻ có giá trị nằm trong đoạn ~[l, r]~, nghĩa là số lượng chỉ số ~i~ thoả mãn ~l \le A_i \le r~.

Dữ liệu vào

• Dòng đầu tiên 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~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~.

Kết quả

In ra ~q~ dòng, dòng thứ ~i~ là đáp án cho truy vấn thứ ~i~.

Ví dụ

Đầu vào:

5 4
2 5 5 5 8
5 5
1 4
6 10
1 10

Đầu ra:

3
1
1
5

Giải thích: Sau khi sắp xếp, các thẻ là ~2, 5, 5, 5, 8~.

• Truy vấn ~[5, 5]~: có ~3~ thẻ ghi số ~5~.
• Truy vấn ~[1, 4]~: chỉ có thẻ ghi ~2~.
• Truy vấn ~[6, 10]~: chỉ có thẻ ghi ~8~.
• Truy vấn ~[1, 10]~: cả ~5~ thẻ.

Giới hạn

• ~1 \le n, q \le 2 \cdot 10^5~
• ~1 \le A_i \le 10^9~
• ~1 \le l \le r \le 10^9~

Đếm trực tiếp từng truy vấn cần ~n \times q~ phép so sánh, lên tới ~4 \cdot 10^{10}~ nên chắc chắn quá thời gian.

Dữ liệu có rất nhiều giá trị lặp lại, và nhiều truy vấn có ~l = r~. Hãy phân biệt cẩn thận giữa "phần tử đầu tiên không nhỏ hơn ~l~" và "phần tử đầu tiên lớn hơn ~r~" — dùng lẫn hai loại biên này sẽ cho kết quả lệch đúng bằng số lần lặp của giá trị ở biên.