Count in Range

Тавсифи масъала

Дан массив $a$ из $n$ целых чисел $a_1, a_2, \dots, a_n$. Необходимо отвечать на запросы вида: «Сколько чисел в массиве имеют значения от $l$ до $r$ включительно?».

Input Format

В первой строке находится целое число $n$ $(1 \le n \le 10^5)$ --- длина массива.

Во второй строке заданы $n$ целых чисел $a_1, a_2, \dots, a_n$ $$ --- элементы массива.

В третьей строке содержится целое число $k$ $(1 \le k \le 10^5)$ --- количество запросов.

Далее следуют $k$ строк, в каждой из которых заданы два целых числа $l$ и $r$ $(−10^9 \le l \le r \le 10^9)$ --- границы очередного запроса.

Output Format

Для каждого запроса выведите одно число --- ответ на него. Все ответы выводите по одному в отдельной строке.

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

4
2
4
5
0
0