e-olymp
Задачи

Сортировка по росту

Сортировка по росту

prb3607

На торжественном открытии олимпиады, впрочем, как и на её закрытии, спортсмены каждой страны были одеты в одинаковые олимпийские костюмы. Естественно, что при таком большом количестве спортсменов, тренеров и обслуживающего персонала, для многих стран сам процесс пошивки олимпийской парадной формы был довольно ответственным и важным делом, и поэтому необходимо было знать рост каждого члена делегации для пошивки формы соответствующего размера. Фирмам, которые будут заниматься пошивом парадной формы, частично повезло, так как известно, что ни в одной делегации не было членов делегации ростом ниже полутора метров и выше двух с половиной.

У вас в распоряжении имеется база данных, в которую занесены рост каждого члена делегации по соответствующему виду спорта. Ваша задача быстро отвечать на запросы типа: А сколько членов делегации имеют рост в пределах от a до b сантиметров?

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

Первая строка каждого запроса содержит единственное число n (1n20000) - количество членов соответствующей делегации. Во второй строке запроса содержится n целых чисел, разделённых единичным пробелом - рост соответствующего члена делегации в сантиметрах. Данные о росте не отсортированы, так как помещались в базу данных в последний момент и не были поэтому обработаны. Третья строка запроса содержит собственно сам запрос: 2 числа - нижняя и верхняя границы интересующего фирму - изготовитель ростового интервала.

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

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

Лимит времени 3 секунды
Лимит использования памяти 128 MiB
Входные данные #1
7
153 168 155 167 155 167 155
165 170
6
189 191 169 190 192 191
165 172
Выходные данные #1
3
1
Источник II Открытая Дистанционная Олимпиада 2012-2013 им. В.Л.Дидковского