D. Вырежи и склей
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У маленького Эхаба есть набор для аппликации, содержащий массив $$$a$$$ длины $$$n$$$. Он планирует взять ножницы и сделать следующее:

  • выбрать отрезок $$$(l, r)$$$, и вырезать каждый элемент $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ на этом отрезке;
  • склеить некоторые из элементов вместе в том же порядке, в котором они шли в массиве;
  • в итоге, получится несколько кусочков, каждый кусочек содержит некоторые элементы, и каждый элемент принадлежит какому-то кусочку.

Более формально, он разделит последовательность $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$ на подпоследовательности. Он считает, что разделение красивое, если для каждого кусочка (подпоследовательности) верно, что если его длина равна $$$x$$$, то никакое значение не встречается строго больше $$$\lceil \frac{x}{2} \rceil$$$ раз в этом кусочке.

Эхаб еще не определился с отрезком, поэтому он интересуется для $$$q$$$ отрезков $$$(l, r)$$$, чему равно минимальное количество кусочков, на которые нужно разделить $$$a_l$$$, $$$a_{l + 1}$$$, ..., $$$a_r$$$, чтобы разделение было красивым.

Последовательность $$$b$$$ является подпоследовательностью массива $$$a$$$, если $$$b$$$ может быть получена из $$$a$$$ удалением нескольких (возможно, ни одного) элементов. Обратите внимание, что она не обязательно должна быть непрерывной.

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

В первой строке даны два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n,q \le 3 \cdot 10^5$$$) — длина массива $$$a$$$ и количество запросов.

Во второй строке даны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n}$$$ ($$$1 \le a_i \le n$$$) — элементы массива $$$a$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — отрезок этого запроса.

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

Для каждого запроса выведите минимальное количество подпоследовательностей, на которые нужно разбить отрезок, чтобы разбиение было красивым. Можно доказать, что такое разбиение всегда существует.

Пример
Входные данные
6 2
1 3 2 3 3 2
1 6
2 5
Выходные данные
1
2
Примечание

В первом запросе можно взять весь массив в одну подпоследовательность, так как его длина равна $$$6$$$, и ни одно значение не встречается в нем больше $$$3$$$ раз.

Во втором запросе элементы отрезка равны $$$[3,2,3,3]$$$. Вы не можете взять их всех в одну подпоследовательность, потому что ее длина будет равна $$$4$$$, и $$$3$$$ встречается в ней больше $$$2$$$ раз. Однако, вы можете разделить отрезок на две подпоследовательности: $$$[3]$$$ и $$$[2,3,3]$$$.