Аналитик изучает стоимость заказов за день. Известны значения n заказов.

Затем поступает q запросов. В каждом запросе заданы две границы x и y, и нужно определить, сколько заказов имеют стоимость в ценовом коридоре от x до y включительно.

Для каждого запроса выведите количество заказов, чьи значения принадлежат диапазону [x, y].

Входные данные

Первая строка содержит целое число n — количество заказов.

Вторая строка содержит n целых чисел a_i — значения заказов.

Третья строка содержит целое число q — количество запросов аналитика.

Каждая из следующих q строк содержит по два целых числа x и y — границы ценового коридора.

Выходные данные

Для каждого запроса выведите одно целое число — количество заказов, значение которых лежит в диапазоне [x, y].

Каждый ответ выводите в отдельной строке.

Ограничения

• 1 <= n <= 2 * 10^5
• -10^9 <= a_i <= 10^9
• 1 <= q <= 2 * 10^5
• x <= y
• |x| <= 10^9
• |y| <= 10^9

Примеры

Пример 1

Входные данные

1
0
1
-100 100

Выходные данные

1

Пример 2

Входные данные

5
-2 -2 0 3 3
6
-2 -2
3 3
-1 2
-1 -1
2 4
3 3

Выходные данные

2
2
1
0
2
2