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 gồm hai số nguyên ~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ử có giá trị thuộc phạm vi giới hạn bởi ~L~ và ~R~.

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

Dữ liệu vào:

• 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[1],A[2],...,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.
  

Ràng buộc:

• ~1 \le N \le 10^5~
• ~1 \le Q \le 10^5~
• ~-10^9 \le A[i] \le 10^9~
• ~1 \le i \le N~
• ~-10^9 \le L \le R \le 10^9~
  

Subtask:

• Subtask 1 (40%): ~N,Q \le 1000~.
• Subtask 2 (30%): ~N,Q \le 10^5~, dãy ~A~ đã được sắp xếp tăng.
• Subtask 3 (30%): ~N,Q \le 10^5~.
  

Dữ liệu ra:

• 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.

Sample input:

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

Sample output:

4
1
2

Giải thích:

• 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]~.