The Third Problem

题意翻译

给定一个 $0\sim n-1$ 的排列 $a$。定义 $0~n-1$ 的排列 $b$ 与 $a$ 相似，当且仅当 $\forall 1\le l\le r\le n$，有 $\operatorname{MEX}_{i=l}^r a_i=\operatorname{MEX}_{i=l}^r b_i$。求与 $a$ 相似的排列个数（$\bmod (10^9+7)$）。 注：一个数列的 $\operatorname{MEX}$ 表示**没有出现在数列中的最小自然数**，如 $\operatorname{MEX}([1,2,3,4,5]) = 0$，$\operatorname{MEX}([0,1,2,4,5]) = 3$。 多测，$t\le10^4$，$1\le n,\sum n\le10^5$，$0\le a_i<n$。 Translated by @Sya_Resory

题目描述

You are given a permutation $ a_1,a_2,\ldots,a_n $ of integers from $ 0 $ to $ n - 1 $ . Your task is to find how many permutations $ b_1,b_2,\ldots,b_n $ are similar to permutation $ a $ . Two permutations $ a $ and $ b $ of size $ n $ are considered similar if for all intervals $ [l,r] $ ( $ 1 \le l \le r \le n $ ), the following condition is satisfied: $ $\operatorname{MEX}([a_l,a_{l+1},\ldots,a_r])=\operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]), $ $ where the $ \\operatorname{MEX} $ of a collection of integers $ c\_1,c\_2,\\ldots,c\_k $ is defined as the smallest non-negative integer $ x $ which does not occur in collection $ c $ . For example, $ \\operatorname{MEX}(\[1,2,3,4,5\])=0 $ , and $ \\operatorname{MEX}(\[0,1,2,4,5\])=3 $ .</p><p>Since the total number of such permutations can be very large, you will have to print its remainder modulo $ 10^9+7 $ .</p><p>In this problem, a permutation of size $ n $ is an array consisting of $ n $ distinct integers from $ 0 $ to $ n-1 $ in arbitrary order. For example, $ \[1,0,2,4,3\] $ is a permutation, while $ \[0,1,1\] $ is not, since $ 1 $ appears twice in the array. $ \[0,1,3\] $ is also not a permutation, since $ n=3 $ and there is a $ 3$ in the array.

输入输出格式

输入格式

Each test contains multiple test cases. The first line of input contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The following lines contain the descriptions of the test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the size of permutation $ a $ . The second line of each test case contains $ n $ distinct integers $ a_1,a_2,\ldots,a_n $ ( $ 0 \le a_i \lt n $ ) — the elements of permutation $ a $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, print a single integer, the number of permutations similar to permutation $ a $ , taken modulo $ 10^9+7 $ .

输入输出样例

输入样例 #1

5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4

输出样例 #1

2
1
1
4
72

说明

For the first test case, the only permutations similar to $ a=[4,0,3,2,1] $ are $ [4,0,3,2,1] $ and $ [4,0,2,3,1] $ . For the second and third test cases, the given permutations are only similar to themselves. For the fourth test case, there are $ 4 $ permutations similar to $ a=[1,2,4,0,5,3] $ : - $ [1,2,4,0,5,3] $ ; - $ [1,2,5,0,4,3] $ ; - $ [1,4,2,0,5,3] $ ; - $ [1,5,2,0,4,3] $ .

**题目大意：**
给定一个从0到n-1的整数排列a。如果对于任意的1≤l≤r≤n，都有区间[a_l,a_{l+1},…,a_r]的MEX等于区间[b_l,b_{l+1},…,b_r]的MEX，那么排列b与排列a相似。求与排列a相似的排列个数（结果对10^9+7取模）。MEX指的是在给定的数列中没有出现的最小非负整数。

**输入数据格式：**
第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
接下来每个测试用例有两行：
- 第一行包含一个整数n（1≤n≤10^5），表示排列a的大小。
- 第二行包含n个不同的整数a_1,a_2,…,a_n（0≤a_i
**输出数据格式：**
对于每个测试用例，输出一个整数，表示与排列a相似的排列个数，结果对10^9+7取模。

**输入输出样例：**
**输入样例 #1：**
```
5
5
4 0 3 2 1
1
0
4
0 1 2 3
6
1 2 4 0 5 3
8
1 3 7 2 5 0 6 4
```
**输出样例 #1：**
```
2
1
1
4
72
```**题目大意：** 给定一个从0到n-1的整数排列a。如果对于任意的1≤l≤r≤n，都有区间[a_l,a_{l+1},…,a_r]的MEX等于区间[b_l,b_{l+1},…,b_r]的MEX，那么排列b与排列a相似。求与排列a相似的排列个数（结果对10^9+7取模）。MEX指的是在给定的数列中没有出现的最小非负整数。 **输入数据格式：** 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 接下来每个测试用例有两行： - 第一行包含一个整数n（1≤n≤10^5），表示排列a的大小。 - 第二行包含n个不同的整数a_1,a_2,…,a_n（0≤a_i