C. Удаление троек
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Устав поддерживать своих дальнобойных сокомандников, Керия теперь составляет задачу на структуру данных, поддерживающую запросы на отрезках.

Для массива $$$b = [b_1, b_2, \ldots, b_m]$$$ длины $$$m$$$, где $$$b_i=0$$$ или $$$b_i=1$$$, рассмотрим следующую операцию удаления троек:

  1. Выберите три индекса $$$1 \le i \lt j \lt k \le m$$$, такие что элементы на этих позициях равны ($$$b_i = b_j = b_k$$$).
  2. Удалите эти три элемента из массива. Стоимость этой операции равняется $$$\min(k-j, j-i)$$$. После удаления оставшиеся части массива конкатенируются, и их индексы перенумеровываются.

Мы хотим сделать массив $$$b$$$ пустым, используя операцию удаления троек. Определим общую стоимость массива как минимально возможную сумму стоимостей операций удаления троек, необходимых для удаления всех элементов массива. Если сделать массив пустым невозможно, стоимость определяется как $$$-1$$$.

Керия хочет протестировать свою структуру данных. Для этого вам нужно ответить на $$$q$$$ независимых запросов. Изначально вам дан массив $$$a = [a_1, a_2, \ldots, a_n]$$$ длины $$$n$$$, где $$$a_i=0$$$ или $$$a_i=1$$$. Для каждого запроса вам дан диапазон $$$1 \le l \le r \le n$$$ и необходимо найти стоимость массива $$$[a_l, a_{l+1}, \ldots, a_r]$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 250\,000$$$) — длина массива и количество запросов.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$a_i = 0$$$ или $$$a_i=1$$$) — элементы массива.

Затем следуют $$$q$$$ строк. $$$i$$$-я из них содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — диапазон подмассива для $$$i$$$-го запроса.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

Гарантируется, что сумма значений $$$q$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк. $$$i$$$-я строка должна содержать одно целое число, представляющее ответ на $$$i$$$-й запрос.

Пример
Входные данные
2
12 4
0 0 1 1 0 1 0 1 0 1 1 0
1 12
2 7
5 10
6 11
6 3
0 0 0 1 1 1
1 3
4 6
1 6
Выходные данные
4
2
3
-1
1
1
2
Примечание

Объяснение первого набора входных данных, первого запроса (1 12):

Подмассив равен $$$[0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0]$$$. В нём шесть $$$0$$$ и шесть $$$1$$$. Возможная оптимальная последовательность операций:

  1. Удалите три $$$1$$$ на индексах $$$3$$$, $$$4$$$, $$$6$$$. Стоимость равна $$$\min(6-4, 4-3) = \min(2, 1) = 1$$$. Массив становится $$$[0, 0, 0, 0, 1, 0, 1, 1, 0]$$$.
  2. Удалите три $$$0$$$ на индексах $$$1$$$, $$$2$$$, $$$3$$$. Стоимость равна $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$. Массив становится $$$[0, 1, 0, 1, 1, 0]$$$.
  3. Удалите три $$$1$$$ на индексах $$$2$$$, $$$4$$$, $$$5$$$. Стоимость равна $$$\min(5-4, 4-2) = \min(1, 2) = 1$$$. Массив становится $$$[0, 0, 0]$$$.
  4. Удалите три $$$0$$$ на индексах $$$1$$$, $$$2$$$, $$$3$$$. Стоимость равна $$$\min(3-2, 2-1) = \min(1, 1) = 1$$$. Массив становится пуст.

Общая стоимость равна $$$1+1+1+1=4$$$.