P13730 【MGVOI R1-B】完美重排（sort）

Siby 同学有一个长度为 $n$ 的数组 $a$，其下标编号为 $1 \sim n$。保证数组 $a$ 是一个长度为 $n$ 的排列，也就是说，$1\sim n$ 中的每个正整数都在数组 $a$ 中出现 **恰好一次**。 在此基础上，Siby 同学定义了 **完美重排** 操作： ::::info[完美重排的定义]{open} * 第一步：选择两个下标 $L,R$（必须满足 $1\le L\le R\le n$）； * 第二步：将 $a_L,...,a_R$ （即数组 $a$ 中下标在 $L$ 和 $R$ 之间的元素）按照 **从小到大** 的顺序重新排序。 :::: 例如，若 $a=[4,3,2,1]$，选择 $L=2,R=4$ 进行一次完美重排操作（也就是将 $a_2,a_3,a_4$ 按照从小到大的顺序排序），得到的新数组为 $a'=[4,1,2,3]$。 接下来，他将进行 $Q$ 组询问（询问之间彼此独立），其中第 $i$ 组询问包含两个参数 $x_i,y_i$（$x_i< y_i$），表示询问你有多少种进行 **恰好一次** 完美重排的方案，使得数组 $a$ 中原先下标为 $x_i$ 的元素，在重排后的下标为 $y_i$。 提示：只要完美重排操作中选择的 $L$ 不同或 $R$ 不同，就被认为是两种不同的方案。

第一行包含两个正整数 $n,Q$，分别表示数组 $a$ 的长度和询问的次数。 第二行包含 $n$ 个正整数，其中第 $i$ 个正整数表示数组 $a$ 中的元素 $a_i$（$1\le a_i\le n$）。 接下来 $Q$ 行，其中第 $i$ 行包含两个正整数 $x_i,y_i$（$1\le x_i< y_i \le n$），表示第 $i$ 组询问的两个参数。

共输出 $Q$ 行。 对于第 $i$ 组询问而言：仅需在第 $i$ 行输出一个非负整数，表示完美重排的方案数。方案应进行恰好一次完美重排，使得数组 $a$ 中原先下标为 $x_i$ 的元素，在重排后的下标为 $y_i$。

**【样例 #1】** ::::info[样例 #1 解释] 此样例下，$a=[3,4,1,2]$。 * 对于第一组询问：只需取 $L=1，R=4$ 进行一次完美重排，就能使得 $a_1$ 在重排后的下标为 $3$（重排前：$a=[\red{3},4,1,2]$，重排后：$a'=[1,2,\red{3},4]$）。可以证明这是唯一的一种方案，故方案数为 $1$； * 对于第二组询问：可以证明，无论如何选取 $L,R$，都不可能使得 $a_1$ 在重排后的下标为 $4$，故方案数为 $0$； * 对于第三组询问： 1. 第一种方案是取 $L=1，R=4$ 进行一次完美重排（重排前：$a=[3,\red{4},1,2]$，重排后：$a'=[1,2,3,\red{4}]$）； 2. 第二种方案是取 $L=2，R=4$ 进行一次完美重排（重排前：$a=[3,\red{4},1,2]$，重排后：$a'=[3,1,2,\red{4}]$），可以验证均满足条件。不存在其它满足条件的方案了，故方案数为 $2$。 :::: **【样例 #2】** ::::info[样例 #2 解释] 此样例下，$a=[6,3,5,7,2,4,1]$。 为了简便，我们用数对 $(i,j)$ 来表示选取 $L=i$，$R=j$ 进行一次完美重排的方案。各组询问对应的所有方案见下表： | 询问编号 | 方案数 | 方案 1 | 方案 2 | 方案 3 | 方案 4 | |:-:|:-:|:-:|:-:|:-:|:-:| | **1** | $2$ | $(1,3)$ | $(1,4)$ | **2** | $1$ | $(1,5)$ | **3** | $0$ | | **4** | $3$ | $(1,7)$ | $(2,5)$ | $(2,6)$ | **5** | $1$ | $(2,7)$ | **6** | $0$ | | **7** | $3$ | $(1,7)$ | $(2,6)$ | $(3,6)$ | **8** | $4$ | $(1,6)$ | $(2,6)$ | $(3,6)$ | $(4,6)$ | **9** | $1$ | $(5,7)$ | | **10** | $2$ | $(5,7)$ | $(6,7)$ | :::: **【样例 #3】** 见附件中的 ```sort/sort3.in``` 与 ```sort/sort3.ans```。 这个样例满足测试点 $7 \sim 12$ 的限制。 **【样例 #4】** 见附件中的 ```sort/sort4.in``` 与 ```sort/sort4.ans```。 这个样例满足测试点 $13 \sim 14$ 的限制。 **【样例 #5】** 见附件中的 ```sort/sort5.in``` 与 ```sort/sort5.ans```。 这个样例满足测试点 $15 \sim 20$ 的限制。 --- **【数据范围】** 对于所有测试点，保证 $2\le n\le 10^4$，$1\le Q\le 2\times 10^3$，$1\le x_i< y_i\le n$，且数组 $a$ 是 $1\sim n$ 的排列。 ::cute-table{tuack} | **测试点编号** | $n \le$ | $Q \le$ | **特殊性质** | |:-:|:-:|:-:|:-:| | $1 \sim 6$ | $20$ | $20$ | 无 | | $7 \sim 12$ | $500$ | $100$ | ^ | | $13 \sim 14$ | $10^4$ | $2\times 10^3$ | **A** | | $15 \sim 20$ | ^ | ^ | 无 | 特殊性质 **A**：保证 $a_i=n-i+1$。 * 分值分配：每个测试点的分值为 $5$ 分。 * 请注意本题特殊的内存限制。