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