4-й этап Республиканской олимпиады по информатике 2022-2023, 2-й тур

Задача D. Массив и запросы

Ограничение по времени:

1.5 секунд

Ограничение по памяти:

256 мегабайт

Абай принес вам простую задачу без легенды. Задан массив $A$, состоящий из $N$ натуральных чисел, а также $Q$ запросов вида $L, R$. Ответом на запрос является максимальное целое $K$ ($K \ge 0$), что для него найдется натуральное $X$, при котором числа $X$, $2X$, $4X$, ..., $2^K \cdot X$ встречаются среди чисел $A_L$, $A_{L+1}$, ..., $A_R$. Ваша задача -- посчитать ответ на каждый запрос. Примечание: натуральным называется целое число больше нуля.

Формат входного файла

В первой строке выходных данных заданы два натуральных числа $N$ и $Q$ ($1 <= N, Q <= 5 \cdot 10^5$). Во второй строке задается массив $A$ ($1 <= A_i <= 10^{18}$). Начиная с третьей строки, задаются запросы $L$, $R$ ($1 <= L <= R <= N$). Каждый запрос задан в отдельной строке.

Формат выходного файла

Выведите $Q$ строк, в $i$-й строке должен быть ответ на $i$-й запрос.

Пример:

Вход

6 3
6 9 12 24 18 9
2 3
4 6
1 5

Ответ

0
1
2

Замечание

Пояснение к примеру: В во втором запросе можно выбрать 18 и 9, тогда $K = 1, X = 9$. В третьем запросе -- 6, 12 и 24 ($K = 2, X = 6$). ( Abay Baimukanov )