B"Tokitsukaze 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 <= q i < j <= q 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 <= q x <= q y <= q r_i ). The first line contains two integers n and q ( 1 <= q n <= q 2 cdot 10^5 ; 1 <= q q <= q 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 <= q p_i <= q n ) -- the permutation p . Each of the next q lines contains two integers l_i and r_i ( 1 <= q l_i <= q r_i <= q n ) -- the segment [l_i,r_i] of this query. For each query, print one integer -- the numbers of beautiful subsegments in the segment [l_i,r_i] . In the first example, for the first query, there are 2 beautiful subsegments -- [1,2] and [1,3] . "...