Tokitsukaze 的排列 $$$p$$$ 长度为 $$$n$$$。
如果存在 $$$i$$$ 和 $$$j$$$ 满足 $$$p_i \cdot p_j = \max\{p_l, p_{l+1}, \ldots, p_r \}$$$,则我们称段 $$$[l,r]$$$ 为美丽,其中 $$$l \leq i < j \leq r$$$。
现在 Tokitsukaze 有 $$$q$$$ 查询,在第 $$$i$$$ 查询中,她想知道 $$$[l_i,r_i]$$$ 段中有多少个漂亮的子段 $$$[x,y]$$$ (即 $$$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]$$$ 段中漂亮子段的数量。
示例
输入 #1
8 3 1 3 5 2 4 7 6 8 1 3 1 1 1 8
输出 #1
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
输出 #2
17 25 1 5 2 0 4 1 0 0
注意
在第一个示例中,对于第一个查询,有 $$$2$$$ 漂亮的子段 - $$$[1,2]$$$ 和 $$$[1,3]$$$。