E. Tokitsukaze и красивые подотрезки
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У Tokitsukaze есть перестановка $$$p$$$ длины $$$n$$$.

Назовем подотрезок $$$[l,r]$$$ красивым, если существуют $$$i$$$ и $$$j$$$, удовлетворяющие $$$p_i \cdot p_j = \max\{p_l, p_{l+1}, \ldots, p_r \}$$$, где $$$l \leq i < j \leq r$$$.

Также у Tokitsukaze есть $$$q$$$ запросов, в $$$i$$$-м запросе она хочет узнать, сколько существует красивых подотрезков $$$[x,y]$$$ на отрезке $$$[l_i,r_i]$$$ (т. е. $$$l_i \leq x \leq y \leq r_i$$$).

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

Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1\leq n \leq 2 \cdot 10^5$$$; $$$1 \leq q \leq 10^6$$$) — длина перестановки $$$p$$$ и количество запросов.

Вторая строка содержит $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — перестановка $$$p$$$.

Каждая из следующих $$$q$$$ строк содержит два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — отрезок $$$[l_i,r_i]$$$ этого запроса.

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

Для каждого запроса выведите одно целое число — количество красивых подотрезков на отрезке $$$[l_i,r_i]$$$.

Примеры
Входные данные
8 3
1 3 5 2 4 7 6 8
1 3
1 1
1 8
Выходные данные
2
0
10
Входные данные
10 10
6 1 3 2 5 8 4 10 7 9
1 8
1 10
1 2
1 4
2 4
5 8
4 10
4 7
8 10
5 9
Выходные данные
17
25
1
5
2
0
4
1
0
0
Примечание

В первом примере для первого запроса есть $$$2$$$ красивых подотрезка — $$$[1,2]$$$ и $$$[1,3]$$$.