CF1699C The Third Problem

给定一个由 $0$ 到 $n-1$ 的整数构成的排列 $a_1,a_2,\ldots,a_n$。你的任务是求有多少个排列 $b_1,b_2,\ldots,b_n$ 与排列 $a$ 是相似的。 对于大小为 $n$ 的两个排列 $a$ 和 $b$，如果对于所有区间 $[l,r]$（$1 \le l \le r \le n$），都满足以下条件，则称 $a$ 和 $b$ 是相似的： $$ \operatorname{MEX}([a_l,a_{l+1},\ldots,a_r]) = \operatorname{MEX}([b_l,b_{l+1},\ldots,b_r]) $$ 其中，$\operatorname{MEX}$ 表示一组整数 $c_1,c_2,\ldots,c_k$ 中未出现的最小非负整数。例如，$\operatorname{MEX}([1,2,3,4,5])=0$，$\operatorname{MEX}([0,1,2,4,5])=3$。 由于相似排列的总数可能非常大，你需要输出其对 $10^9+7$ 取模的结果。 在本题中，长度为 $n$ 的排列是指由 $0$ 到 $n-1$ 的 $n$ 个互不相同的整数按任意顺序组成的数组。例如，$[1,0,2,4,3]$ 是一个排列，而 $[0,1,1]$ 不是排列，因为 $1$ 出现了两次。$[0,1,3]$ 也不是排列，因为 $n=3$ 时数组中出现了 $3$。

每组测试数据包含多组测试用例。输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。接下来的若干行描述每组测试用例。 每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——排列 $a$ 的长度。 第二行包含 $n$ 个互不相同的整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i < n$）——排列 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每组测试用例，输出一个整数，表示与排列 $a$ 相似的排列个数，对 $10^9+7$ 取模。

对于第一个测试用例，唯一与 $a=[4,0,3,2,1]$ 相似的排列是 $[4,0,3,2,1]$ 和 $[4,0,2,3,1]$。 对于第二个和第三个测试用例，给定的排列只与自身相似。 对于第四个测试用例，与 $a=[1,2,4,0,5,3]$ 相似的排列有 $4$ 个： - $[1,2,4,0,5,3]$； - $[1,2,5,0,4,3]$； - $[1,4,2,0,5,3]$； - $[1,5,2,0,4,3]$。 由 ChatGPT 4.1 翻译