AT_abc379_f [ABC379F] Buildings 2

[problemUrl]: https://atcoder.jp/contests/abc379/tasks/abc379_f 有 $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 完成