CF1677E Tokitsukaze and Beautiful Subsegments

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 \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 $ ).

The 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.

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] $ .