У 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]\).
В первом примере для первого запроса есть \(2\) красивых подотрезка — \([1,2]\) и \([1,3]\).
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
4000 ms 1024 Mb Правила оформления программ и список ошибок при автоматической проверке задач