E. Tokitsukaze and Beautiful Subsegmentstime limit per test4 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputTokitsukaze has a permutation p of length n.Let's call a segment [l,r] beautiful if there exist i and j satisfying p_i \cdot p_j = \max\{p_l, p_{l+1}, \ldots, p_r \}, where l \leq i < j \leq r.Now Tokitsukaze has q queries, in the i-th query she wants to know how many beautiful subsegments [x,y] there are in the segment [l_i,r_i] (i. e. l_i \leq x \leq y \leq r_i).InputThe first line contains two integers n and q (1\leq n \leq 2 \cdot 10^5; 1 \leq q \leq 10^6) — the length of permutation p and the number of queries.The second line contains n distinct integers p_1, p_2, \ldots, p_n (1 \leq p_i \leq n) — the permutation p.Each of the next q lines contains two integers l_i and r_i (1 \leq l_i \leq r_i \leq n) — the segment [l_i,r_i] of this query.OutputFor each query, print one integer — the numbers of beautiful subsegments in the segment [l_i,r_i].ExamplesInput
8 3
1 3 5 2 4 7 6 8
1 3
1 1
1 8
Output
2
0
10
Input
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
Output
17
25
1
5
2
0
4
1
0
0
NoteIn the first example, for the first query, there are 2 beautiful subsegments — [1,2] and [1,3].
8 3
1 3 5 2 4 7 6 8
1 3
1 1
1 8

2 0 10 
['data structures', '*2900']