Permutations with Bounded Longest Decreasing Subsequence

You are given a permutation \(p_1, p_2, \ldots, p_n\) consisting of the numbers \(1,2,\ldots,n\). There are \(q\) queries. The \(i\)th query is given by two integers \(L_i\) and \(R_i\) with \(1 \le L_i \le R_i \le n\). For each query, consider the sequence \(p_{L_i}, p_{L_i+1}, \ldots, p_{R_i}\) as a fixed prefix of length \(k = R_i-L_i+1\) of a permutation of \(\{1,2,\ldots,n\}\). Count the number of ways to complete this prefix to a full permutation of \(\{1,2,\ldots,n\}\) such that the full permutation has its longest decreasing subsequence of length at most 2. Two permutations are considered different if they differ in at least one position. Since the answer can be very large, output it modulo \(10^9+7\).

Definition. For a sequence \(a_1,a_2,\ldots,a_k\), its longest decreasing subsequence is the maximum integer \(t\) such that there exist indices \(1\le s_1<s_2<\cdots a_{s_2} > \cdots > a_{s_t}. \]

Remark. A permutation has its longest decreasing subsequence of length at most 2 if and only if it does not contain a triple \(x>y>z\) in increasing order of indices (i.e. it is 321-avoiding). It is known that such permutations have a nice structure and can be characterized by a greedy two‐chain procedure. In this problem the prefix is fixed and you have to count the number of valid completions.

Approach. A common method is to simulate the greedy algorithm which works as follows on a permutation \(a_1, a_2,\ldots,a_n\):

1. Maintain two increasing sequences (chains) A and B, initially empty, and process elements in order.
2. For the current element \(x\): if \(x\) is greater than the last element of chain A (or if chain A is empty), append \(x\) to A; otherwise, if \(x\) is greater than the last element of chain B (or B is empty), append \(x\) to B; otherwise, the permutation is invalid.

The fixed prefix determines the initial state (the last element in chain A and B) as well as the set of used numbers. Then, the problem reduces to counting the number of orders in which the remaining numbers can be appended such that the above greedy procedure never fails. We solve this by a state DP where the state is defined by a bitmask representing the used numbers and the current last elements in chain A and B.

inputFormat

The first line contains two integers \(n\) and \(q\) (the size of the permutation and the number of queries). The second line contains \(n\) distinct integers \(p_1, p_2, \ldots, p_n\) --- a permutation of \(\{1,2,\ldots,n\}\). Each of the next \(q\) lines contains two integers \(L_i\) and \(R_i\) describing a query.

outputFormat

For each query, output one integer: the number of valid completions modulo \(10^9+7\).

sample

4 2
1 3 2 4
1 2
2 4

2
1

</p>