题目描述

小英雄在探险时发现了 $n$ 个宝藏物品，每个物品都有其特定的价值。

为了准确评估这批宝藏的档次，小英雄需要使用价值探测器进行多次统计。

每次统计时，小英雄会指定一个价值范围 $[L, R]$，探测器需要快速统计出价值在这个范围内的宝藏物品数量。

由于宝藏数量庞大且统计次数很多，小英雄需要一个高效的算法来完成这个任务。

输入格式

第一行输入一个整数 $n$，表示宝藏物品的总数量。
第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示每个宝藏物品的价值。
第三行输入一个整数 $t$，表示需要进行的统计次数。
接下来 $t$ 行，每行包含两个整数 $L$ 和 $R$，表示一次统计的价值区间。

输出格式

输出 $t$ 行，每行一个整数，表示对应价值区间 $[L, R]$ 内的宝藏物品数量。

样例

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

4
5

样例解释

• 第一次统计 $[2, 5]$：有价值为 $2, 3, 4, 5$ 的物品，共 $4$ 个。
• 第二次统计 $[3, 7]$：有价值为 $3, 4, 5, 6, 7$ 的物品，共 $5$ 个。

数据范围

• 对于 $30\%$ 的数据：$1 \le n \le 5000$，$1 \le a_i \le 1000$，$1 \le t \le 5000$，$1 \le L \le R \le 1000$。
• 对于 $60\%$ 的数据：$1 \le n \le 10^5$，$1 \le a_i \le 10^6$，$1 \le t \le 10^5$，$1 \le L \le R \le 10^6$。
• 对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le a_i \le 10^9$，$1 \le t \le 10^5$，$1 \le L \le R \le 10^9$。