Tại thành phố Thời Tiết Xanh, Viện Khí tượng đang nghiên cứu dữ liệu lịch sử về nhiệt độ để dự báo biến đổi khí hậu. Họ đã ghi lại nhiệt độ của \(n\) ngày liên tiếp vào một mảng \(A\), trong đó phần tử thứ \(i\) biểu thị nhiệt độ của ngày thứ \(i\).

Các nhà khoa học quan tâm đến một ngưỡng nhiệt độ quan trọng cố định là \(x\) (những ngày có nhiệt độ lớn hơn hoặc bằng \(x\) được gọi là "ngày nắng gắt"). Họ đưa ra \(q\) câu hỏi, mỗi câu hỏi có dạng một khoảng thời gian từ ngày \(L\) đến ngày \(R\). Nhiệm vụ của bạn là giúp Viện Khí tượng đếm xem trong khoảng thời gian từ ngày \(L\) đến ngày \(R\) có bao nhiêu ngày là "ngày nắng gắt".

Input

• Dòng đầu tiên gồm ba số nguyên dương \(n\), \(x\) và \(q\) (\(1 \le n, q \le 2\cdot 10^5\), \(1 \le x \le 10^9\)) — lần lượt là số ngày, ngưỡng nhiệt độ cố định, và số lượng truy vấn.
• Dòng thứ hai gồm \(n\) số nguyên \(A_1, A_2, \dots, A_n\) (\(1 \le A_i \le 10^9\)) — nhiệt độ của các ngày từ ngày 1 đến ngày \(n\).
• \(q\) dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L\) và \(R\) (\(1 \le L \le R \le n\)) — mô tả một truy vấn khoảng thời gian.

Output

• In ra \(q\) dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng (số lượng ngày có nhiệt độ \(\ge x\) trong đoạn từ \(L\) đến \(R\)).

Example

5 30 3
25 32 30 28 35
1 5
2 4
3 5

3
2
2