P10100 [ROIR 2023] 石头 (Day 2)

翻译自 [ROIR 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

Bob 面前排列着 $n$ 个黑色石头，从 $1$ 到 $n$ 编号。第 $i$ 个石头上写有一个整数 $a_i$，$n$ 个石头上写的整数构成了一个排列。我们称第 $i$ 个石头的相邻石头为第 $(i-1)$ 个和第 $(i+1)$ 个石头（如果存在的话）。 Bob 按照以下步骤进行 $n$ 次操作： - 在第一步，选择任意的 $i$（$1\le i\le n$），并将第 $i$ 个石头涂成白色。 - 在第 $2$ 到第 $n$ 步，选取相邻石头中至少有一个白色石头的黑色石头中的 $a_i$ 最小的石头 $j$（即，可能有很多个黑色石头满足它的相邻石头中至少有一个白色石头，但是要选取其中 $a_i$ 最小的那个），并将其涂成白色。 很容易看出，在执行完所有步骤后，$n$ 个石头都是白色的。 Alice 选择了 $q$ 对值 $p_j$ 和 $k_j$。对于每对 $p$ 和 $k$ 的值，她想知道有多少种不同的选择第一步时将哪块石头涂成白色的方式，使得第 $p$ 块石头在第 $k$ 步变成白色。 帮助 Bob 回答 Alice 的 $q$ 个查询。

第一行包含两个整数 $n$ 和 $q$，分别表示石头的数量和查询的数量。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示写在石头上的整数。 接下来的 $q$ 行，每行包含一对整数 $p_j$ 和 $k_j$。

对于每个查询，输出一个整数，表示查询的答案。

下面的样例解释中加粗的数是被涂成白色的。 在第一个样例中： - 如果第一步选择第 $1$ 块石头： - 第 $1$ 步：$[\bold1, \gray4, \gray6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $2$ 块石头： - 第 $1$ 步：$[\gray1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $3$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \bold6, \gray5, \gray2, \gray3]$； - 第 $2$ 步：$[\gray1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $3$ 步：$[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$； - 第 $4$ 步：$[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$； - 第 $5$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $4$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \bold5, \gray2, \gray3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \gray3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $5$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \gray3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 - 如果第一步选择第 $6$ 块石头： - 第 $1$ 步：$[\gray1, \gray4, \gray6, \gray5, \gray2, \bold3]$； - 第 $2$ 步：$[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$； - 第 $3$ 步：$[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$； - 第 $4$ 步：$[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$； - 第 $5$ 步：$[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$； - 第 $6$ 步：$[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$。 本题使用捆绑测试。 | 子任务编号 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n,q\le300$ | | $2$ | $17$ | $n\le3000$ | | $3$ | $12$ | $n\le50000,q\le10$ | | $4$ | $6$ | $a_i$ 的值递增 | | $5$ | $16$ | 所有 $k_i$ 相等 | | $6$ | $15$ | 所有 $p_i$ 相等 | | $7$ | $14$ | 无特殊性质 | 对于 $100\%$ 的数据，$2 \le n \le 10^5$，$1 \le q \le 10^5$，$1 \le a_i \le n$ 且所有 $a_i$ 互不相同，$1 \le p_j,k_j \le n$。