Городские счётчики по диапазону

В городе Нумероград у каждого здания есть номер (целое число). Мэр расставил датчики и теперь часто спрашивает: «Сколько зданий имеют номер между двумя указанными числами?»

Чтобы не перебирать весь город каждый раз, помоги отвечать на запросы быстро.

Формат ввода

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

Если в запросе l > r, мэр всё равно имеет в виду числа между ними, то есть диапазон [min(l, r), max(l, r)].

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

Выведи q строк. В каждой строке — количество зданий, номер которых лежит в диапазоне [l, r] (включая границы).

Ограничения

• 1 ≤ n ≤ 20000
• 1 ≤ q ≤ 20000
• 1 ≤ ai ≤ 1 000 000
• 1 ≤ l, r ≤ 1 000 000

Пример

Ввод:

5 3
1 3 3 7 10
1 3
4 9
10 10

Вывод:

3
1
1

Ключевое наблюдение: если номера зданий отсортировать, то все значения из диапазона [l, r] окажутся в массиве одним непрерывным блоком. Значит, задача сводится к тому, чтобы быстро найти первый индекс, где число >= l, и первый индекс, где число > r. Разность этих индексов и есть количество подходящих зданий.

Почему работает двоичный поиск: в отсортированном массиве условие «элемент уже >= l» (или «элемент уже > r») меняется один раз, поэтому границу можно найти за log n.

План решения:

• Прочитать n, q и массив номеров.
• Отсортировать массив.
• Для каждого запроса:
• привести границы к правильному порядку: l, r = min(l, r), max(l, r).
• найти left = lower_bound(l) (в Python это bisect_left).
• найти right = upper_bound(r) (в Python это bisect_right).
• ответ: right - left.

Мини-сниппет формулы: ans = bisect_right(a, r) - bisect_left(a, l)

Сложность: сортировка O(n log n), каждый запрос O(log n), итого O(n log n + q log n).

Частая ошибка: перепутать включённость границ. Для диапазона «включая l и r» нужен именно bisect_left для l и bisect_right для r (а не два bisect_left). Также не забудь обработать случай l > r.