题目描述

我有很多很多（$n$ 条）用魔法合成的珍珠项链……（其实神仙比凡人更爱美），每天起来我都要从中挑一条戴上……挑哪条很有讲究，如果比情敌的难看，那么就会被……，如果比天后 Hera 的好看，那么就完蛋了。所以我希望你能帮帮我，解决这个令人头疼的问题——每天帮我算算，那天我能戴的项链有多少条。

输入格式

第一行一个正整数 $n$，表示项链总条数。
第二行 $n$ 个整数，代表每条项链的好看程度 $X_i$。
第三行一个正整数 $m$，表示总天数（即总询问次数）。
接下来 $m$ 行，每行两个整数 $A_i, B_i$，询问好看程度在 $A_i$ 到 $B_i$ 之间的项链条数（含等于 $A_i$ 或 $B_i$，$A_i$ 与 $B_i$ 大小关系不确定，可能 $A_i > B_i$）。

输出格式

输出 $m$ 行，对于每次询问输出一行一个整数，表示好看程度在 $A_i$ 到 $B_i$ 之间的项链条数。

样例

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

3
4
7
1
0
3

数据范围

对于 $25\%$ 的数据，$m, n \le 1000$。
对于 $100\%$ 的数据，$m, n \le 100000$，$0 \le X_i \le 10^9$，$1 \le A_i, B_i \le 10^9$。