Дан массив a из n целых чисел a1, a2,..., an. Научитесь быстро отвечать на запросы «Сколько чисел имеют значения от l до r»?
Входные данные
В первой строке находится целое число n (1<=n<=105) — длина массива. Во второй строке находятся n целых чисел a1, a2,..., an (−109<=ai<=109). В третьей строке находится целое число k (1<=k<=105) — число запросов. В следующих k строках находятся пары чисел l r (−109<=l<=r<=109).
Выходные данные
Выведите k чисел (каждое в отдельной строке) - ответы на запросы.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5
10 1 10 3 4
4
1 10
2 9
3 4
2 2
|
5
2
2
0
|