У 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\)).
Выходные данные
Для каждого запроса выведите одно целое число — количество красивых подотрезков на отрезке \([l_i,r_i]\).
Примечание
В первом примере для первого запроса есть \(2\) красивых подотрезка — \([1,2]\) и \([1,3]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8 3
1 3 5 2 4 7 6 8
1 3
1 1
1 8
|
2
0
10
|
|
2
|
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
|