题目描述

译自 ROI Regional 2023 Day2 T3. Камни

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

鲍勃执行以下 ( n ) 个步骤：

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

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

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

输入格式

第一行输入包含两个整数 ( 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 )$ 步被涂成白色的不同方法的数量。

样例 1

输入

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 ) 步：$([\mathbf{1},\mathbf{4},\mathbf{6},\mathbf{5},\mathbf{2},\mathbf{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}])$

数据范围与提示

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