103795: [Atcoder]ABC379 F - Buildings 2

Problem Statement

There are $N$ buildings, building $1$, building $2$, $\ldots$, building $N$, arranged in this order in a straight line from west to east. Building $1$ is the westernmost, and building $N$ is the easternmost. The height of building $i\ (1\leq i\leq N)$ is $H_i$.

For a pair of integers $(i,j)\ (1\leq i\lt j\leq N)$, building $j$ can be seen from building $i$ if the following condition is satisfied.

• There is no building taller than building $j$ between buildings $i$ and $j$. In other words, there is no integer $k\ (i\lt k\lt j)$ such that $H_k > H_j$.

You are given $Q$ queries. In the $i$-th query, given a pair of integers $(l_i,r_i)\ (l_i\lt r_i)$, find the number of buildings to the east of building $r_i$ (that is, buildings $r_i + 1$, $r_i + 2$, $\ldots$, $N$) that can be seen from both buildings $l_i$ and $r_i$.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. The $i$-th line ($1 \leq i \leq Q$) should contain the answer to the $i$-th query.

Sample Input 1

5 3
2 1 4 3 5
1 2
3 5
1 4

Sample Output 1

2
0
1

• For the first query, among the buildings to the east of building $2$, buildings $3$ and $5$ can be seen from both buildings $1$ and $2$, so the answer is $2$.
• For the second query, there are no buildings to the east of building $5$.
• For the third query, among the buildings to the east of building $4$, building $5$ can be seen from both buildings $1$ and $4$, so the answer is $1$.

Sample Input 2

10 10
2 1 5 3 4 6 9 8 7 10
3 9
2 5
4 8
5 6
3 8
2 10
7 8
6 7
8 10
4 10

Sample Output 2

1
3
1
2
1
0
1
1
0
0

问题陈述

有$N$栋建筑，分别是建筑$1$、建筑$2$、$\ldots$、建筑$N$，它们按从西到东的顺序排列成一条直线。建筑$1$是最西边的，建筑$N$是最东边的。建筑$i\ (1\leq i\leq N)$的高度是$H_i$。

对于一对整数$(i,j)\ (1\leq i\lt j\leq N)$，如果满足以下条件，那么从建筑$i$可以看到建筑$j$。

• 在建筑$i$和建筑$j$之间没有比建筑$j$更高的建筑。换句话说，不存在整数$k\ (i\lt k\lt j)$使得$H_k > H_j$。

你将得到$Q$个查询。在第$i$个查询中，给定一对整数$(l_i,r_i)\ (l_i\lt r_i)$，找出从建筑$r_i$向东的建筑（即建筑$r_i + 1$、$r_i + 2$、$\ldots$、$N$）中，能同时从建筑$l_i$和建筑$r_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$
• 所有输入值都是整数。

输入

输入从标准输入以以下格式给出：

$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$个查询的答案。

示例输入 1

5 3
2 1 4 3 5
1 2
3 5
1 4

示例输出 1

2
0
1

• 对于第一个查询，在建筑$2$以东的建筑中，建筑$3$和建筑$5$能同时从建筑$1$和建筑$2$看到，所以答案是$2$。
• 对于第二个查询，没有建筑在建筑$5$以东。
• 对于第三个查询，在建筑$4$以东的建筑中，建筑$5$能同时从建筑$1$和建筑$4$看到，所以答案是$1$。

示例输入 2

10 10
2 1 5 3 4 6 9 8 7 10
3 9
2 5
4 8
5 6
3 8
2 10
7 8
6 7
8 10
4 10

示例输出 2

1
3
1
2
1
0
1
1
0
0