Permutations

给定一个 $1, 2, \dots, n$ 的排列 $p[1], p[2], \dots, p[n]$。你需要回答 $q$ 个询问。

第 $i$ 个询问（$i \in \{1, \dots, q\}$）由两个数字 $L[i]$ 和 $R[i]$ 描述（$1 \le L[i] \le R[i] \le n$）。该询问的答案是以序列 $p[L[i]], p[L[i] + 1], \dots, p[R[i] - 1], p[R[i]]$ 开头的长度为 $n$ 的排列的数量，且这些排列还需满足其最长下降子序列的长度不超过 2。由于答案可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

对于一个序列 $a[1], a[2], \dots, a[k]$，其最长下降子序列的长度是满足以下性质的最大整数 $t$：存在 $t$ 个下标 $s[1], s[2], \dots, s[t]$，满足 $1 \le s[1] < s[2] < \dots < s[t] \le k$ 且 $a[s[1]] > a[s[2]] > \dots > a[s[t]]$。

输入格式

第一行包含数字 $n$。 第二行包含数字 $p[1], \dots, p[n]$，即区间 $[1, n]$ 内的 $n$ 个不同整数。 第三行包含数字 $q$。 接下来的 $q$ 行指定了询问：第 $i$ 行（$i \in \{1, \dots, q\}$）包含数字 $L[i]$ 和 $R[i]$。

输出格式

对于每个询问，输出排列数量对 $10^9 + 7$ 取模的结果。每个结果占一行。

数据范围

• $1 \le n \le 3 \cdot 10^5$
• $1 \le q \le 3 \cdot 10^5$

子任务

1. (6 分) $n \le 10, q \le 10$。
2. (7 分) $n \le 1000, q \le 1000$。每个询问的区间内都包含 $p[j] = n$。
3. (9 分) 每个询问的区间内都包含 $p[j] = n$。
4. (12 分) $n \le 1000, q \le 1000$。对于每个 $i \in \{1, \dots, n\}$，满足 $p[i] = i$，且对于每个 $j \in \{1, \dots, q\}$，满足 $L[j] = 1$。
5. (18 分) 对于每个 $i \in \{1, \dots, n\}$，满足 $p[i] = i$，且对于每个 $j \in \{1, \dots, q\}$，满足 $L[j] = 1$。
6. (12 分) $n \le 1000, q \le 1000$。
7. (36 分) 无附加限制。

样例

输入 1

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

输出 1

4
5
1
0

说明

对于第一个询问，考虑以 4 开头且最长下降子序列长度不超过 2 的序列 $\langle 1, 2, 3, 4, 5 \rangle$ 的排列。共有四个，分别是： $\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$。