P11164 [BalkanOI 2023] Permutations

**译自 [BalkanOI 2023](https://boi2023.zotks.si) Day1 T3「[Permutations](https://boi2023.zotks.si/wp-content/uploads/day_1/d1_permutations/en_EN.pdf)」** 给你一个由数字 $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}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$ 取模的结果。

### 样例解释 对于第一个查询，考虑到有四个序列 $\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}$ 详细子任务附加限制及分值如下表所示。 | 子任务编号 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $n \leq 10, q \leq 10$ | $6$ | | $2$ | $n \leq 1000, q \leq 1000$，每个查询的区间内都包含 $p_{j}=n$ | $7$ | | $3$ | 每个查询的区间内都包含 $p_{j}=n$ | $9$ | | $4$ | $n \leq 1000, q \leq 1000$，$p_{i}=i\ (1\leq i\leq n)$，$L_{j}=1\ (1\leq j\leq q)$ | $12$ | | $5$ |$p_{i}=i\ (1\leq i \leq n)$，$L_{j}=1\ (1\leq j\leq q)$ | $18$ | | $6$ | $n \leq 1000, q \leq 1000$ | $12$ | | $7$ | 无附加限制 | $36$ |