题目背景

翻译自 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$。