Cho dãy A gồm n số nguyên a₁, a₂, …, a_n và một số nguyên dương x. Cho q truy vấn có dạng

l, r.

Yêu cầu: với mỗi truy vấn l, r hãy đếm số lượng các số có giá trị dương và nhỏ hơn x từ phần tử thứ l đến phần tử thứ r của dãy số A.

Input

• Dòng thứ nhất ghi 3 số nguyên dương n, x, q (1 ≤ n, x, q ≤ 10⁵)
• Dòng thứ hai ghi n số nguyên a₁, a₂, …, a_n, số thứ i có giá trị là a_i (1 ≤ i ≤ n; |a_i| ≤ 10⁵)
• Q dòng tiếp theo, mỗi dòng chứa hai số nguyên dương l, r (1 ≤ l ≤ r ≤ 10⁵) Các số trên cùng một dòng ghi cách nhau một dấu cách.

Output: gồm q dòng, mỗi dòng ghi một số nguyên là kết quả tìm được tương ứng với mỗi truy vấn.

Ràng buộc:

• Có 50% số test ứng với 50% số điểm có q = 1
• 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.