e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

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

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

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 им. В.Л.Дидковского