题目描述

明日复明日，明日何其多。在魔法学院刻苦学习的小C，希望珍惜当下的每一天，学习到足够多的知识。因为小 C 每天的学习状态都会不一样，既不能选择太简单的课程浪费学习时间，又不能选择超出自己学习能力范围的深奥课程。那么，如何在浩瀚的图书馆中选择合适难度的课程真是一项大工程，你能帮他编个程序计算他每天能学习的课程有多少门吗？

输入格式

第一行为一个正整数 n ，表示图书馆内有多少门课程。

第二行为 n 个整数，第 i 个整数为第 i 门课程的难度 a[i] 。( 0 <= a[i] <= max long int )

第三行为一个正整数 m ，表示小 C 学习的天数。

接下来 m 行，每行两个整数 $X_i$ ，$Y_i$ ，表示小 C 在第 i 天能学习到的最低难度 $X_i$ 和最高难度 $Y_i$ （0 <= $X_i$ <= $Y_i$ <= max long int ）。

输出格式

M 行，每行一个整数，表示小 C 每天能学习的课程门数。

样例

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

4
0
8
2
3

数据范围

对于 40% 的数据，1 ≤ n , m ≤ 1000；

对于 100% 的数据，1 ≤ n , m ≤ 100000。