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.

题目描述

在鲍勃面前有一排 $n$ 块黑色石头，编号从 $1$ 到 $n$。第 $i$ 块石头上写着一个整数 $a_{i}$。对于每个从 $1$ 到 $n$ 的数字，恰好有一个石头上写着这个数字，换句话说，数字 $a_{i}$ 形成了一个排列。我们称第 $i$ 块石头的相邻石头为 $(i-1)$ 和 $(i+1)$（如果它们存在）。

鲍勃执行以下 $n$ 个步骤：

• 第一步，鲍勃从 $1$ 到 $n$ 中选择一个任意的 $i$，并将第 $i$ 块石头涂成白色。
• 从第 $2$ 步到第 $n$ 步，鲍勃查看所有至少有一个相邻白色石头的黑色石头，从中选择 $a_{j}$ 最小的石头 $j$，并将其涂成白色。

很容易看出，执行完所有步骤后，鲍勃面前将有 $n$ 块白色石头。

爱丽丝选择了 $q$ 对值 $p_{j}$ 和 $k_{j}$。对于每对值，她想知道有多少种不同的方法可以选择第一步的石头，使得编号为 $p_{j}$ 的石头恰好在第 $k_{j}$ 步被涂成白色。

请帮助鲍勃回答爱丽丝的 $q$ 个查询。

输入格式

第一行输入包含两个整数 $n$ 和 $q$ $(2 \leq n \leq 10^5, 1 \leq q \leq 10^5)$，分别表示石头的数量和查询的数量。

第二行输入包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$1 \leq a_{i} \leq n$，所有 $a_{i}$ 都不同）。

接下来的 $q$ 行中，每行包含一对整数 $p_{j}$ 和 $k_{j}$ $(1 \leq p_{j} \leq n, 1 \leq k_{j} \leq n)$，表示石头的编号和该石头在第 $k_{j}$ 步被涂成白色。

输出格式

对于每个查询，输出一个整数，表示如果第 $i$ 块石头在第一步被涂成白色，那么编号为 $p_{j}$ 的石头在第 $k_{j}$ 步被涂成白色的不同方法的数量。

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

1
2
1
2

在第一个样例中，操作如下：

• 如果第一步选择第 $1$ 块石头：第 $1$ 步：$[\mathbf{1},4,6,5,2,3]$，第 $2$ 步：$[\mathbf{1},\mathbf{4},6,5,2,3]$，第 $3$ 步：$[\mathbf{1}, \mathbf{4}, \mathbf{6}, 5,2,3]$，第 $4$ 步：$[\mathbf{1}, \mathbf{4}, \mathbf{6}, \mathbf{5}, 2,3]$，第 $5$ 步：$[\mathbf{1}, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, 3]$，第 $6$ 步：$[\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$。
• 如果第一步选择第 $2$ 块石头：第 $1$ 步：$[1,\mathbf{4},6,5,2,3]$，第 $2$ 步：$[\mathbf{1},\mathbf{4},6,5,2,3]$，第 $3$ 步：$[\mathbf{1}, \mathbf{4},\mathbf{6},5,2,3]$，第 $4$ 步：$[\mathbf{1}, \mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$，第 $5$ 步：$[\mathbf{1}, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, 3]$，第 $6$ 步：$[\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$。
• 如果第一步选择第 $3$ 块石头：第 $1$ 步：$[1,4,\mathbf{6},5,2,3]$，第 $2$ 步：$[1,\mathbf{4},\mathbf{6},5,2,3]$，第 $3$ 步：$[\mathbf{1}, \mathbf{4},\mathbf{6},5,2,3]$，第 $4$ 步：$[\mathbf{1}, \mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$，第 $5$ 步：$[\mathbf{1}, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, 3]$，第 $6$ 步：$[\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$。
• 如果第一步选择第 $4$ 块石头：第 $1$ 步：$[1,4,6,\mathbf{5},2,3]$，第 $2$ 步：$[1,4,6,\mathbf{5},\mathbf{2},3]$，第 $3$ 步：$[1,4,6, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $4$ 步：$[1,4, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $5$ 步：$[1, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $6$ 步：$[\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$。
• 如果第一步选择第 $5$ 块石头：第 $1$ 步：$[1,4,6,5, \mathbf{2}, 3]$，第 $2$ 步：$[1,4,6,5, \mathbf{2}, \mathbf{3}]$，第 $3$ 步：$[1,4,6, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $4$ 步：$[1,4, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $5$ 步：$[1, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $6$ 步：$[1,4,6,5,2,3]$。
• 如果第一步选择第 $6$ 块石头：第 $1$ 步：$[1,4,6,5,2, \mathbf{3}]$，第 $2$ 步：$[1,4,6,5, \mathbf{2}, \mathbf{3}]$，第 $3$ 步：$[1,4,6, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $4$ 步：$[1,4, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $5$ 步：$[1, \mathbf{4}, \mathbf{6}, \mathbf{5}, \mathbf{2}, \mathbf{3}]$，第 $6$ 步：$[\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{3}]$。

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

0
1
1

数据范围与提示

详细子任务附加限制及分值如下表所示。