CF2207E2.N-MEX (Counting Version)

Builder Base Attack (Stage 2) — Supercell, Clash of Clans

This is the counting version of the problem. The difference between the versions is that in this version, you need to count the number of constructions where $0 \leq b_i \leq n$. You can hack only if you solved all versions of this problem.

The Master Builder doesn't like repetitive tasks — repairing the base, upgrading the town hall fifteen times, and doing yet more programming problems about MEX. So, this is not going to be your ordinary MEX problem.

For any positive integer $k$, define the $k$-mex of a collection of integers $S$ to be the $k$-th smallest nonnegative integer not present in $S$. For instance, the $1$-mex and $2$-mex of $[1, 2, 1]$ are $0$ and $3$, respectively.

Let $n$ be a positive integer, and consider an array of nonnegative integers $[a_1, \ldots, a_n]$. Compute the number of arrays of nonnegative integers $[b_1, \ldots, b_n]$ such that:

• For all $1 \leq i \leq n$, the $(n-i+1)$-mex of $[b_1, \ldots, b_i]$ is $a_i$.
• Additionally, for all $1 \leq i \leq n$, $0 \leq b_i \leq n$.

Since the number of such arrays may be large, output the answer modulo $10^9 + 7$.

建筑大师基地进攻（第二阶段）——Supercell，《部落冲突》

本题为计数版本。与其它版本的区别在于：在本版本中，你需要统计满足 $0 \leq b_i \leq n$ 的构造方案总数。仅当你已解决本题的所有版本后，才可进行 Hack。

建筑大师讨厌重复性工作——修缮基地、将城镇大厅升级十五次、以及再做一道关于 MEX 的编程题。因此，本题将不是你所熟悉的普通 MEX 问题。

对任意正整数 $k$，定义整数集合 $S$ 的 $k$-mex 为 $S$ 中未出现的第 $k$ 小的非负整数。例如，数组 $[1, 2, 1]$ 的 $1$-mex 和 $2$-mex 分别为 $0$ 和 $3$。

设 $n$ 为一正整数，考虑一个由非负整数组成的数组 $[a_1, \ldots, a_n]$。请计算满足如下条件的非负整数数组 $[b_1, \ldots, b_n]$ 的个数：

• 对所有 $1 \leq i \leq n$，$[b_1, \ldots, b_i]$ 的 $(n-i+1)$-mex 等于 $a_i$；
• 此外，对所有 $1 \leq i \leq n$，均有 $0 \leq b_i \leq n$。

由于满足条件的数组个数可能极大，请将答案对 $10^9 + 7$ 取模后输出。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($0 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$0 \leq a_i \leq 10^9$）。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the number of satisfying arrays $b$ modulo $10^9 + 7$.

对于每个测试用例，输出一个整数——满足条件的数组 $b$ 的个数对 $10^9 + 7$ 取模的结果。

In the first test case, the array $a = [3, 3, 1]$. There exist exactly six such arrays $b$ that work. One such example is the array $b = [2, 0, 2]$, which satisfies the conditions because:

• the $3$-mex of $[b_1] = [2]$ is $a_1 = 3$,
• the $2$-mex of $[b_1, b_2] = [2, 0]$ is $a_2 = 3$,
• the $1$-mex of $[b_1, b_2, b_3] = [2, 0, 2]$ is $a_3 = 1$.

In the second test case, the array $a = [2, 1, 3]$. It can be shown that no suitable array $b$ exists.

在第一个测试用例中，数组 $a = [3, 3, 1]$。恰好存在六个满足条件的数组 $b$。其中一个例子是数组 $b = [2, 0, 2]$，它满足条件，因为：

• $[b_1] = [2]$ 的 $3$-mex 为 $a_1 = 3$，
• $[b_1, b_2] = [2, 0]$ 的 $2$-mex 为 $a_2 = 3$，
• $[b_1, b_2, b_3] = [2, 0, 2]$ 的 $1$-mex 为 $a_3 = 1$。

在第二个测试用例中，数组 $a = [2, 1, 3]$。可以证明，不存在满足条件的数组 $b$。