该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

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

输入格式

• 第一行输入一个整数 n（1 ≤ n ≤ 10^5），表示宝藏物品的总数量。
• 第二行输入 n 个整数 a₁, a₂, ..., aₙ（1 ≤ aᵢ ≤ 10^9），表示每个宝藏物品的价值。
• 第三行输入一个整数 t（1 ≤ t ≤ 10^5），表示需要进行的统计次数。
• 接下来 t 行，每行包含两个整数 L 和 R（1 ≤ L ≤ R ≤ 10^9），表示一次统计的价值区间。

输出格式

• 输出 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 ≤ n ≤ 5,000，1 ≤ aᵢ ≤ 1,000，1 ≤ t ≤ 5,000，1 ≤ L ≤ R ≤ 1,000。
• 对于 60% 的数据：1 ≤ n ≤ 100,000，1 ≤ aᵢ ≤ 1,000,000，1 ≤ t ≤ 100,000，1 ≤ L ≤ R ≤ 1,000,000。
• 对于 100% 的数据：1 ≤ n ≤ 100,000，1 ≤ aᵢ ≤ 10^9，1 ≤ t ≤ 100,000，1 ≤ L ≤ R ≤ 10^9。