Cho dãy \(A\) gồm \(n\) số nguyên dương \(a_{1},\ a_{2},..,a_{n}\ \) và 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.

Dữ liệu vào:

- Dòng thứ nhất ghi 3 số nguyên dương \(n,\ x\) và \(q\) \((1 \leq n,x,q \leq 10^{5})\)

- Dòng thứ hai ghi \(n\) số nguyên \(a_{1},a_{2},\ \ldots,a_{n}\) các số có giá trị tuyệt đối không vượt quá \(10^{5}\)

- \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(l,\ r\ (1 \leq l \leq r \leq n)\)

Dữ liệu ra:

- \(q\) dòng mỗi dòng ghi một số nguyên dương là kết quả tìm được của mỗi truy vấn

Ví dụ

Input	Output
9 6 2 8 -1 6 5 -2 7 -3 4 -8 1 6 4 9	1 2

Giới hạn: có 50% test có \(n \leq \ 10^{3}\)