Một nhà máy sản xuất có ~N~ công nhân, trong một tháng mỗi công nhân hoàn thành được số sản phẩm lần lượt là ~a_1, a_2, ..., a_N~. Để đánh giá năng suất làm việc của các công nhân, người ta thống kê xem có bao nhiêu công nhân sản xuất được số sản phẩm trong khoảng [~p~, ~q~].

Yêu cầu: Em hãy giúp nhà máy thống kê số công nhân có số sản phẩm thoả mãn yêu cầu trên.

Dữ liệu vào:

• Dòng đầu tiên ghi số ~N~ là số công nhân của nhà máy, ~T~ (~n ≤ 10^5~, ~T ≤ 10^5~) là số khoảng [~p~, ~q~] cần thống kê.
• Dòng tiếp theo ghi ~n~ số nguyên dương lần lượt là các giá trị ~a_1,a_2…,a_n (a_i ≤ 10^9~).
• ~T~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~p~, ~q~ (~p, q ≤10^9~).

Dữ liệu ra:

• Gồm ~T~ dòng, mỗi dòng là kết quả tương ứng với từng khoảng [~p, q~]

Ví dụ:

Input

5 3 
1 3 5 7 9 
2 6 
1 10
10 20

Output

2
5
0

Ràng buộc:

• 30% test thỏa ~2 ≤ n ≤ 100~
• 40% test thỏa ~2 ≤ n ≤ 1000~
• 30% test thỏa ~2 ≤ n ≤ 100000~