Truy vấn

Sau buổi học về chuyên đề dãy số, Nam được hướng dẫn các thao tác xử lí và lưu trữ dãy số trong ngôn ngữ lập trình: Xóa, chèn, tìm kiếm, thay thế, sắp xếp... các phần tử hoặc các đoạn con trên dãy số.

Để ứng dụng kiến thức đã học, Nam được giao nhiệm vụ thực hiện bài toán: Cho dãy \(a\) gồm \(n\) số nguyên dương \(a_1, a_2, \ldots, a_n\) và số nguyên dương \(x\). Cho \(q\) truy vấn có dạng \(l, r\). Thầy giáo yêu cầu Nam 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\).

Yêu cầu: Hãy đếm số lượng các số dương nhỏ hơn \(x\) từ \(l\) đến \(r\) của dãy \(a\).

Input

Dữ liệu vào gồm

• Dòng thứ nhất ghi \(3\) số nguyên dương \(n, x\) và \(q\) (\(1 \le n, x, q \le 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 \(l, r\) (\(1 \le l \le r \le n\)).

Ràng buộc:

• Subtask 1: Có \(50\%\) test tương ứng với \(50\%\) điểm với \(n \le 10^3\);

• Subtask 2: Có \(50\%\) test tương ứng với \(50\%\) điểm với \(10^3 < n \le 10^5\).

Output

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

Example

Input:

10 7 4
8 -1 6 5 -2 7 -3 4 -8 9
1 6
4 9
3 8
5 10

Output:

2
2
3
1

Note

Dãy \(a = [8, -1, 6, 5, -2, 7, -3, 4, -8, 9]\), \(x = 7\). Các số dương nhỏ hơn \(7\) là \(6, 5, 4\) (ở vị trí \(3, 4, 8\)).

Truy vấn \(1\ 6\): có \(6\) và \(5\), đáp án \(2\). Truy vấn \(4\ 9\): có \(5\) và \(4\), đáp án \(2\). Truy vấn \(3\ 8\): có \(6, 5, 4\), đáp án \(3\). Truy vấn \(5\ 10\): chỉ có \(4\), đáp án \(1\).