Фермер Джон разместил свои \(N\) (\(1 \leq N \leq 100,000\)) стогов сена в
различных точках одномерной дороги вдоль его фермы. Вам требуется ответить
на \(Q\) (\(1 \leq Q \leq 100,000\)) запросов, о том сколько стогов сена находится
внутри указанного участка дороги.
ФОРМАТ ВВОДА (файл haybales.in):
Первая строка содержит
\(N\) и
\(Q\).
Следующая строка содержит \(N\) различных целых чисел, каждое в интервале
\(0 \ldots 1,000,000,000\), указывающих местоположения стогов сена.
Каждая из последующих \(Q\) строк содержит два целых числа \(A\) и \(B\)
(\(0 \leq A \leq B \leq 1,000,000,000\)) задающих запрос на количество стогов
сена между \(A\) и \(B\), включительно.
ФОРМАТ ВЫВОДА (файл haybales.out):
Вы должны вывести \(Q\) строк. Для каждого запроса выведите количество
стогов сена в соответствующем интервале.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 6
3 2 7 5
2 3
2 4
2 5
2 7
4 6
8 10
|
2
2
3
4
1
0
|