e-olymp
Задачі

Сортування за зростом

Сортування за зростом

prb3607

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

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

Вхідні дані

Перший рядок кожного запиту містить єдине число n (1n20000) - кількість членів відповідної делегації. У другому рядку запиту міститься n цілих чисел, відокремлених одиничним пропуском - зріст відповідного члена делегації у сантиметрах. Дані про зріст не відсортовані, так як заносились у базу даних у останній момент і тому не були опрацьовані. Третій рядок запиту містить власне сам запит: 2 числа - нижню та верхню границі ростового інтервалу, який цікавить фірму-виробника. Запити продовжуються до кінця файлу.

Вихідні дані

Для кожного запиту у окремому рядку виведіть відповідь на нього.

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