Cho mảng số nguyên ~a~ độ dài ~n~ và ~q~ truy vấn, mỗi truy vấn bao gồm hai số nguyên ~l~ và ~r~, yêu cầu đếm xem trong mảng có bao nhiêu phần tử có giá trị nằm trong đoạn ~[l,r]~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(n,q \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên mảng ~a~ ~(0 \le a_i \le 10^9)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~l~ và ~r~ ~(0 \le l \le r \le 10^9)~ mô tả truy vấn.

Output

• Với mỗi truy vấn, in ra trên một dòng là số lượng phần tử có giá trị nằm trong đoạn ~[l,r]~.

Samples

Sample Input 1

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

Sample Output 1

2
2
3
4
1
0

Scoring

• Subtask ~1~ ~-~ ~50~ điểm: ~n,q \le 1000~
• Subtask ~2~ ~-~ ~50~ điểm: Không còn ràng buộc gì thêm