AT_abc379_f.[ABC379F] Buildings 2

有 $N$ 栋建筑从西向东依次排列，编号为建筑 $1$ 到建筑 $N$，其中建筑 $1$ 位于最西侧，建筑 $N$ 位于最东侧。建筑 $i$（$1 \leq i \leq N$）的高度为 $H_i$。

对于整数对 $(i,j)$（$1 \leq i < j \leq N$），当满足以下条件时，可以从建筑 $i$ 看到建筑 $j$：

• 在建筑 $i$ 和建筑 $j$ 之间不存在比建筑 $j$ 更高的建筑。即，不存在整数 $k$（$i < k < j$）满足 $H_k > H_j$。

现在需要回答 $Q$ 个询问。第 $i$ 个询问给出整数对 $(l_i, r_i)$（$l_i < r_i$），要求统计在建筑 $r_i$ 东侧的建筑（即建筑 $r_i+1$, 建筑 $r_i+2$, $\ldots$, 建筑 $N$）中，能够同时从建筑 $l_i$ 和建筑 $r_i$ 看到的建筑数量。

输入通过标准输入给出，格式如下：

$N$ $Q$
$H_1$ $H_2$ $\ldots$ $H_N$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

输出 $Q$ 行。第 $i$ 行（$1 \leq i \leq Q$）输出第 $i$ 个询问的答案。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq H_i \leq N$
• $H_i \neq H_j$（$i \neq j$）
• $1 \leq l_i < r_i \leq N$
• 输入中的所有值均为整数

样例解释 #1

• 对于第一个询问，在建筑 $2$ 东侧的建筑中，能够同时从建筑 $1$ 和建筑 $2$ 看到的建筑有建筑 $3$ 和建筑 $5$，共 $2$ 栋。
• 对于第二个询问，建筑 $5$ 东侧没有建筑。
• 对于第三个询问，在建筑 $4$ 东侧的建筑中，能够同时从建筑 $1$ 和建筑 $4$ 看到的建筑只有建筑 $5$，共 $1$ 栋。

翻译由 DeepSeek V3 完成