题目描述

译自 BalkanOI 2023 Day1 T3「Permutations」

给你一个由数字 $1,2, \ldots, n$ 组成的排列 $p_{1}, p_{2}, \ldots, p_{n}$。你需要回答 $q$ 个查询。

第 $i\ (1\leq i\leq q)$ 个查询由两个数字 $L_{i},R_{i}\ (1 \leq L_{i} \leq R_{i} \leq n)$ 表示。你需要回答满足以下条件的排列个数：

• 排列的长度为 $n$；
• 以序列 $p_{L_{i}}, p_{L_{i}+1}, \ldots, p_{R_{i}-1}, p_{R_{i}}$ 作为开头；
• 排列的最长递减子序列的长度至多为 $2$。

由于答案可能很大，输出它们对 $10^{9}+7$ 取模的结果。

对于一个序列 $a_{1}, a_{2}, \ldots, a_{k}$，它的最长递减子序列的长度是最大的整数 $t$，使得存在 $t$ 个下标 $s_{1}, s_{2}, \ldots, s_{t}$，满足 $1 \leq s_{1}<s_{2}<\ldots<s_{t} \leq k$ 且 $a_{s_{1}}>a_{s_{2}}>\ldots>a_{s_{t}}$。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $p_{1}, \ldots, p_{n}$，即区间 $[1, n]$ 中的 $n$ 个不同的整数。

第三行包含一个整数 $q$。

接下来的 $q$ 行每行描述了一个查询。第 $i\ (1\leq i\leq q)$ 行包含两个整数字 $L_{i}$ 和 $R_{i}$。

输出格式

对于每个查询输出单独的一行，表示打印排列的个数对 $10^{9}+7$ 取模的结果。

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

4
5
1
0

提示

样例解释

对于第一个查询，考虑到有四个序列 $\langle 1,2,3,4,5\rangle$ 的排列以 $4$ 开始，并且它们的最长递减子序列的长度至多为 $2$。这些排列是：

• $\langle 4,1,2,3,5\rangle$；
• $\langle 4,1,2,5,3\rangle$；
• $\langle 4,1,5,2,3\rangle$；
• $\langle 4,5,1,2,3\rangle$。

数据范围

对于所有输入数据，满足：

• $1 \leq n \leq 3 \cdot 10^{5}$
• $1 \leq q \leq 3 \cdot 10^{5}$

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