Một nhà khoa học đã ghi lại dữ liệu đo lường vào một dãy ~A~ gồm ~N~ giá trị, với mỗi phần tử ~A[i]~ là kết quả đo ở vị trí thứ ~i~. Do tính chất của thí nghiệm, bạn sẽ nhận được ~Q~ lần yêu cầu truy vấn. Mỗi truy vấn bao gồm hai ngưỡng giá trị ~L~ và ~R~. Nhiệm vụ của bạn là xác định xem trong dãy ~A~, có bao nhiêu phần tử mà giá trị của nó thuộc phạm vi giới hạn bởi ~L~ và ~R~?

Yêu cầu: Hãy đếm số lượng phần tử của dãy ~A~ thỏa mãn ~L \le A[i] \le R~.

Input

• Dòng đầu tiên chứa hai số nguyên dương: ~N~ (số phần tử của dãy ~A~) và ~Q~ (số lần truy vấn).

• Dòng thứ hai chứa ~N~ số nguyên, là các phần tử của dãy ~A~: ~A[1], A[2], \dots, A[N]~.

• Tiếp theo là ~Q~ dòng, mỗi dòng mô tả một truy vấn gồm hai số nguyên: ~L~ và ~R~. Các số trên cùng một dòng cách nhau bởi dấu cách.

Output

In ~Q~ dòng, mỗi dòng chứa số lượng phần tử trong dãy ~A~ thỏa mãn điều kiện phạm vi của truy vấn tương ứng.

Scoring

Sample Input 1

6 3
10 3 5 8 3 5
3 5
10 12
3 3

Sample Output 1

4
1
2

Notes

• Truy vấn 1 ~(3, 5)~: Có ~4~ phần tử thỏa mãn là ~3, 5, 3, 5~.

• Truy vấn 2 ~(10, 12)~: Có ~1~ phần tử thỏa mãn là ~10~.

• Truy vấn 3 ~(3, 3)~: Có ~2~ phần tử thỏa mãn là ~3, 3~.