F. Очередная задача про запросы на перестановках
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Устали от длинных условий?...

Вам дана перестановка $$$p$$$ длины $$$n$$$, а также $$$m$$$ запросов.

Каждый запрос представляется границами $$$1 \leq l \leq r \leq n$$$, в ответ вам надо сказать количество пар $$$l \leq i, j \leq r$$$, $$$i \neq j$$$ таких, что $$$p_i$$$ является делителем $$$p_j$$$.

Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от 1 до $$$n$$$ в произвольном порядке. Например, [2,3,1,5,4] — перестановка, но [1,2,2] не перестановка (2 встречается в массиве дважды) и [1,3,4] тоже не перестановка ($$$n=3$$$, но в массиве встречается 4).

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

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

Во второй строке вам даны $$$n$$$ чисел $$$p_i$$$ — элементы перестановки ($$$1 \le p_i \le n$$$).

В последующих $$$m$$$ строках даны запросы, по два целых числа $$$l_i$$$, $$$r_i$$$ — границы запроса ($$$1 \le l_i \le r_i \le n$$$).

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

Выведите $$$m$$$ строк, в $$$i$$$-й из которых ответ на $$$i$$$-й запрос.

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

В первом запросе искомыми парами индексов будут (2, 5), (4, 5), (4, 3); 6 делится на 3, 6 делится на 2, 4 делится на 2.