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

ADA University - March 7 - Segment Tree

Интервальный запрос меньше

Имеется массив целых чисел длины n. Вам следует ответить на q запросов: сколько чисел из интервала [l, r] имеют значение меньше x.

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

Первая строка содержит длину массива n (1n105). Следующая строка содержит n чисел. В следующей строке задано количество q (1q105) запросов. Каждая из следующих q строк содержит один запрос: три целых числа l, r и x (lr, 1x109).

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

Для каждого запроса выведите в отдельной строке количество чисел из интервала [l, r], которые меньше x.

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
8
1 3 2 4 3 10 5 5
4
1 8 5
1 4 3
5 8 9
2 6 4
Выходные данные #1
5
2
3
3