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

Tokitsukaze 有一个长度为 $n$ 的排列 $p$。

我们称一个区间 $[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$ 个询问中，她想知道区间 $[l_i,r_i]$ 中有多少个优美的子区间 $[x,y]$（即满足 $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.

第一行包含两个整数 $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]$。

For each query, print one integer — the numbers of beautiful subsegments in the segment $[l_i,r_i]$.

对于每个查询，输出一个整数——区间 $[l_i,r_i]$ 中优美子区间的个数。

In the first example, for the first query, there are $2$ beautiful subsegments — $[1,2]$ and $[1,3]$.

在第一个例子中，对于第一个查询，有 $2$ 个优美的子段——$[1,2]$ 和 $[1,3]$。