You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 ROIR 2023 D2T3。

题目描述

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$。

输出格式

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

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

1
2
1
2

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

0
1
1

提示

下面的样例解释中加粗的数是被涂成白色的。

在第一个样例中：

• 如果第一步选择第 $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]$。

本题使用捆绑测试。

对于 $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$。