Спринты на стадионе

На школьном стадионе тренер записал результаты спринтов по дням. Иногда он спрашивает: «А сколько в этом отрезке дней были *по-настоящему быстрыми* — строго быстрее заданного порога?»

Ваша задача — быстро отвечать на такие вопросы.

Формат ввода

В первой строке два целых числа n и q — число дней и число вопросов. Во второй строке n целых чисел a1, a2, ..., an — результат в каждый день. Далее идут q строк, в каждой три целых числа l r t.

Это означает: посчитать, сколько значений ai на позициях l..r строго больше t.

Формат вывода

Выведите q строк. В i-й строке — ответ на i-й вопрос.

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ q ≤ 20000
• 0 ≤ ai ≤ 1000
• 1 ≤ l ≤ r ≤ n
• 0 ≤ t ≤ 1000

Пример

Ввод:

5 3
2 5 1 4 3
1 5 3
2 4 1
3 3 0

Вывод:

2
2
1

Ключевое наблюдение: запрос «сколько ai на l..r строго больше t» — это про порог. Если рассматривать t от большого к маленькому, то множество индексов с ai > t только растёт: при уменьшении t добавляются новые дни.

Приём: оффлайн-обработка (сначала читаем все запросы, потом отвечаем) + дерево Фенвика (BIT) для быстрых подсчётов количества отмеченных индексов на отрезке. BIT хранит 1 в позиции i, если день уже «достаточно быстрый», иначе 0. Тогда ответ — сумма на отрезке.

План:

• Сохрани пары (ai, i) для всех дней и отсортируй по ai по убыванию.
• Сохрани запросы как (t, l, r, id) и тоже отсортируй по t по убыванию (id нужен, чтобы вернуть ответы в исходном порядке).
• Заведи указатель p по отсортированным дням и пустой BIT.
• Идя по запросам в порядке убывания t:
• Пока p < n и текущий день имеет ai > t, добавь его индекс в BIT: add(pos, +1), сдвинь p.
• Ответ для запроса: sum(r) - sum(l-1).
• Выведи ответы по id.

Сложность: сортировки O((n+q) log(n+q)), обновления и запросы BIT — O((n+q) log n).

Частая ошибка: перепутать строгость — нужно именно ai > t, а не >=. Ещё следи за 1-индексацией в BIT и формулой sum(r) - sum(l-1).