Description

You are given a permutation $p[1], p[2], \ldots, p[n]$ of the numbers $1,2, \ldots, n$. You need to answer $q$ queries.

The $i$-th query (for $i \in\{1, \ldots, q\}$ ) is described by the numbers $L[i]$ and $R[i]$ ($1 \leq L[i] \leq R[i] \leq n$). The answer to the query is the number of permutations of length $n$ that start with the sequence $p[L[i]], p[L[i]+1], \ldots, p[R[i]-1], p[R[i]]$ and that, additionally, satisfy the property that the length of their longest decreasing subsequence is at most $2$. Since the answers can be very large, output them modulo $10^{9}+7$.

For a sequence $a[1], a[2], \ldots, a[k]$, the length of the longest decreasing subsequence is the greatest integer $t$ such that there are $t$ indices $s[1], s[2], \ldots, s[t]$ with the properties $1 \leq s[1]<s[2]<\ldots<s[t] \leq k$ and $a[s[1]]>a[s[2]]>\ldots>a[s[t]]$.

Input format

The first line contains the number $n$.

The second line contains the numbers $p[1], \ldots, p[n]$, i.e., $n$ distinct integers from the interval $[1, n]$.

The third line contains the number $q$.

The next $q$ lines specify the queries: the $i$-th of those lines, for $i \in\{1, \ldots, q\}$, contains the numbers $L[i]$ and $R[i]$.

Output format

For each query, print the number of permutations modulo $10^{9}+7$. Each should be on a separate line.

Input bounds

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

Subtasks

1. (6 points) $n \leq 10, q \leq 10$.
2. (7 points) $n \leq 1000, q \leq 1000$. Each query contains $p[j]=n$ in its interval.
3. (9 points) Each query contains $p[j]=n$ in its interval.
4. (12 points) $n \leq 1000, q \leq 1000$. For each $i \in\{1, \ldots, n\}$, $p[i]=i$, and for each $j \in\{1, \ldots, q\}$ ,$L[j]=1$.
5. (18 points) For each $i \in\{1, \ldots, n\}, p[i]=i$, and for each $j \in\{1, \ldots, q\}, L[j]=1$.
6. (12 points) $n \leq 1000, q \leq 1000$.
7. (36 points) No additional constraints.

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

4
5
1
0

For the first query, consider that there are four permutations of the sequence $\langle 1,2,3,4,5\rangle$ that start with $4$ and have the length of the longest decreasing subsequence at most $2￥. These are:

• $\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$.