题目描述

鲍勃面前有一排 $n$ 个黑色石子，编号为 $1$ 到 $n$。第 $i$ 个石子上写着整数 $a_i$。已知 $a_1,a_2,\ldots,a_n$ 是一个 $1$ 到 $n$ 的排列。

称第 $i$ 个石子的邻居为第 $i-1$ 个和第 $i+1$ 个石子（如果存在）。

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

1. 第一步，鲍勃任选一个位置 $i$，将第 $i$ 个石子染成白色。
2. 从第 $2$ 步到第 $n$ 步，鲍勃考虑所有仍为黑色、且与至少一个白色石子相邻的石子。在这些石子中，他选择 $a_j$ 最小的石子 $j$，并将其染成白色。

显然，$n$ 步结束后所有石子都会变成白色。

爱丽丝给出 $q$ 个询问，每个询问包含一对数 $p_j,k_j$。对于每个询问，她想知道：有多少种第一步选择的初始石子位置 $i$，会使得编号为 $p_j$ 的石子恰好在第 $k_j$ 步变成白色。

请回答所有询问。

输入格式

第一行包含两个整数 $n,q$（$2\le n\le 10^5$，$1\le q\le 10^5$）。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$，且所有 $a_i$ 两两不同）。

接下来 $q$ 行，每行包含两个整数 $p_j,k_j$（$1\le p_j\le n$，$1\le k_j\le n$），表示一个询问。

输出格式

对每个询问输出一个整数：满足条件的初始位置数量。

子任务

样例 1

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

1
2
1
2

样例 2

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

0
1
1