题目描述

给定 $n$ 个正整数：$a_1,...,a_n$ 与正整数 $k$，请你回答 $q$ 个问题——子段 $a_{l_i},...,a_{r_i}$ 中有多少个小于 $k$ 的数字？

输入格式

第一行三个正整数 $n,k,q$。
第二行 $n$ 个正整数 $a_1,...,a_n$。
接着 $q$ 行每行两个正整数 $l_i,r_i$。

输出格式

$q$ 行，每行一个整数表示结果。

样例 #1

样例输入 #1

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

样例输出 #1

3
2
1

提示

• 对于 $50\%$ 数据：$1 \leq l_i \leq r_i \leq n \leq 10^2$，$1 \leq q \leq 10^2$，$1 \leq a_i,k \leq 10^3$。
• 对于 $100\%$ 数据：$1 \leq l_i \leq r_i \leq n \leq 10^6$，$1 \leq q \leq 10^5$，$1 \leq a_i,k \leq 10^9$。