题目描述

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$。

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

1
0
2

7 10
6 3 5 7 2 4 1
1 3
1 4
1 7
2 3
2 4
2 5
3 5
4 6
5 6
6 7

2
1
0
3
1
0
3
4
1
2

提示

【样例 #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)$			$(4,6)$
9	$1$	$(5,7)$
10	$2$		$(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$		无
$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$ 分。

• 请注意本题特殊的内存限制。