У маленького Эхаба есть набор для аппликации, содержащий массив \(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\) удалением нескольких (возможно, ни одного) элементов. Обратите внимание, что она не обязательно должна быть непрерывной.
Выходные данные
Для каждого запроса выведите минимальное количество подпоследовательностей, на которые нужно разбить отрезок, чтобы разбиение было красивым. Можно доказать, что такое разбиение всегда существует.
Примечание
В первом запросе можно взять весь массив в одну подпоследовательность, так как его длина равна \(6\), и ни одно значение не встречается в нем больше \(3\) раз.
Во втором запросе элементы отрезка равны \([3,2,3,3]\). Вы не можете взять их всех в одну подпоследовательность, потому что ее длина будет равна \(4\), и \(3\) встречается в ней больше \(2\) раз. Однако, вы можете разделить отрезок на две подпоследовательности: \([3]\) и \([2,3,3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 2
1 3 2 3 3 2
1 6
2 5
|
1
2
|