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

Для массива $$$b=[b_1,b_2,\ldots,b_m]$$$ длины $$$m$$$ ($$$b_i \geq 2$$$) рассмотрим следующую игру для двух игроков, в которой участвуют Поби и Рекклес.

  • Игроки ходят по очереди, при этом первым ходит Поби.
  • Поби в свой ход должен выбрать элемент $$$x \ge 2$$$ и заменить его на $$$\left\lfloor \frac{x}{2} \right\rfloor$$$. Другими словами, он выбирает $$$i$$$ ($$$1 \leq i \leq m$$$) такой, что $$$b_i \ge 2$$$, а затем присваивает $$$b_i := \left\lfloor \frac{b_i}{2} \right\rfloor$$$.
  • Рекклес в свой ход должен выбрать элемент $$$x \ge 2$$$ из массива $$$b$$$ и заменить его на $$$x+1$$$. Другими словами, он выбирает $$$i$$$ ($$$1 \leq i \leq m$$$) такой, что $$$b_i \ge 2$$$, а затем присваивает $$$b_i := b_i+1$$$.

Игра заканчивается, как только все элементы массива $$$b$$$ становятся $$$1$$$.

Определим счёт игры как количество ходов, которые сделает Поби. Цель Поби — минимизировать счёт игры, в то время как цель Рекклеса — максимизировать счёт.

Таким образом, значение массива $$$b$$$ — это счёт игры, когда оба игрока играют оптимально.

Вам дан массив целых чисел $$$a$$$ длины $$$n$$$ ($$$a_i \ge 2$$$).

Ответьте на $$$q$$$ независимых запросов. В каждом запросе вам дан диапазон $$$1 \leq l \leq r \leq 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$$$ ($$$2 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

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

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

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

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

Пример
Входные данные
2
5 5
4 3 2 5 6
1 1
1 2
2 4
3 5
1 5
10 1
314 159 265 358 979 323 846 264 338 327
1 10
Выходные данные
2
3
5
6
10
91
Примечание

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

Подмассив равен $$$[4]$$$.

  1. Поби: $$$4\to \left\lfloor \tfrac{4}{2}\right\rfloor=2$$$. Массив равен $$$[2]$$$.
  2. Рекклес: $$$2\to 3$$$. Массив равен $$$[3]$$$.
  3. Поби: $$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$. Массив равен $$$[1]$$$, игра заканчивается.

Можно показать, что эта стратегия оптимальна для обоих игроков. Следовательно, значение массива $$$[4]$$$ равно $$$2$$$.

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

Подмассив равен $$$[4,3]$$$.

  1. Поби: $$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$. Массив равен $$$[4,1]$$$.
  2. Рекклес: $$$4\to 5$$$. Массив равен $$$[5,1]$$$.
  3. Поби: $$$5\to \left\lfloor \tfrac{5}{2}\right\rfloor=2$$$. Массив равен $$$[2,1]$$$.
  4. Рекклес: $$$2\to 3$$$. Массив равен $$$[3,1]$$$.
  5. Поби: $$$3\to \left\lfloor \tfrac{3}{2}\right\rfloor=1$$$. Массив равен $$$[1,1]$$$, игра заканчивается.

Можно показать, что эта стратегия оптимальна для обоих игроков. Следовательно, значение массива $$$[4,3]$$$ равно $$$3$$$.