题意

给你一个长度为 $n$ 的排列 $a$ ，请你找出有多少个相同长度的排列 $b$ 和 $a$ 相似。

如果对于所有区间 $[l, r] (1 \le l \le r \le n)$ ，下面的条件满足：

$\operatorname{MEX}(a_l, a_{l + 1}, \ldots , a_r) = \operatorname{MEX}(b_l, b_{l + 1}, \ldots , b_r)$

我们就称排列 $a$ 和 $b$ 是相似的。

其中 $\operatorname{MEX}$ 对于数组 $c$ 的定义是：最小的，没有出现在 $c$ 中的非负整数 $x$ 。

例如 $\operatorname{MEX}([1,2,3,4,5]) = 0 \ \operatorname{MEX}([0,1,2,4,5]) = 3$ 。

由于答案可能会很大，所以输出时需要打印答案模 $10^9 + 7$ 的结果。

思路

直接想答案可能比较难，可以先模拟一下给出的样例，尝试构造出一些 $b$ 。

$a = [1, 3, 7, 2, 5, 0, 6, 4]$

我们从 $0$ 这个数字开始考虑样例。可以发现在 $b$ 中， $0$ 的位置一定和 $a$ 中的 $0$ 的位置相等。

为什么呢？我们定义在 $a$ 中数字 $i$ 出现的位置为 $\text{pos}_i$ ，比如 $\text{pos}_0 = 6$ （下标从 $1$ 开始）。

这时，选择 $[\text{pos}_0, \text{pos}_0]$ 的区间对比 $a$ 和 $b$ 的 $\operatorname{MEX}$ 是否相等，首先，在 $a$ 中，因为 $a[\text{pos}_0] = 0$ ， $a$ 的 $\operatorname{MEX}([\text{pos}_0])$ 一定等于 $1$ 。

如果 $b$ 的 $0$ 的位置被改变了，那么在 $b$ 中，因为 $a[\text{pos}_0] > 0$ ， $\operatorname{MEX}([\text{pos}_0])$ ，就一定等于 $0$ 了。

所以我们可以推断出 $0$ 的位置是不能变的。

我们还能推出， $1$ 的位置也是不能改变的。

可以考虑 $[\text{pos}_1(1), \text{pos}_0(6)] (1\ 3\ 7\ 2\ 5\ 0)$ 和 $[\text{pos}_1 + 1, \text{pos}_0](3\ 7\ 2\ 5\ 0)$ 这两个区间的 $\operatorname{MEX}$ 值。

因为 $1$ 的存在， $\operatorname{MEX}([\text{pos}_1, \text{pos}_0])$ 一定大于 $1$ ，而因为有 $0$ 并且没有 $1$ $\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0])$ 一定等于 $1$ 。

架设我们在 $b$ 中改变了 $1$ 的位置，比如改到了 $2$ ，那么在 $b$ 中， $\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0](1\ 7\ 2\ 5\ 0))$ 就大于 $1$ 了，不符合 $a$ 中等于 $1$ 的情况。

现在考虑能合法放置 $2$ 的位置。我们可以推断出，如果在 $a$ 中 $2 \in (\text{pos}_1, \text{pos}_0)$ ，那么在 $b$ 中， $2$ 就可以被放在 $(\text{pos}_1, \text{pos}_0)$ 这个区间的任意位置。

为啥呢？我们设区间 $[l, r]$ 在 $a$ 中包含 $0$ 和 $1$ ，也就是 $l \le \text{pos}_1, \text{pos}_0 \le r$ 。

那因为在 $a$ 中 $2 \in (\text{pos}_1, \text{pos}_0)$ ，a 中所有 $[l, r]$ 的 $\operatorname{MEX}$ 一定大于 $2$ （也就是说，在 $a$ 中，一个区间如果同时包含 $0$ 和 $1$ ，就一定会包含 $2$ ）。

同时，在 $a$ 中，不符合 $l \le \text{pos}_1, \text{pos}_0 \le r$ 的其他所有区间的 $\operatorname{MEX}$ 最大只有 $1$ ，（这样的区间最多包含一个 $0$ ，那么 $\operatorname{MEX}$ 就是 $1$ 了）。

那么在 $b$ 中，只要 $2 \in (\text{pos}_1, \text{pos}_0)$ ，就能符合 $\operatorname{MEX}([l, r]) > 2$ 。并且符合在不动其他数字的位置的情况下 $a$ 和 $b$ 相似。

符合这样的位置一共有 $(\text{pos}_0 - \text{pos}_1 + 1) - 2$ 个（ $-2$ 是因为 $0$ 和 $1$ 占用了区间内的两个位置）。

那么如果在 $a$ 中， $2 \notin (\text{pos}_1, \text{pos}_0)$ 呢？

比如 $a = [1, 3, 7, 6, 0, 5, 2, 4]$

我们可以推断出，和前面讲的 $0$ 和 $1$ 一样，这种情况下，我们需要在 $b$ 中把 $2$ 放到相同的位置上。

考虑 $[\text{pos}_1, \text{pos}_2]$ 这个区间，其 $\operatorname{MEX}$ 一定大于 $2$ 。而 $[\text{pos}_1, \text{pos}_2 - 1]$ 这个区间的 $\operatorname{MEX}$ 就一定等于 $2$ （包含 $0$ ， $1$ ）。

假设我们把 $2$ 放到 $\text{pos}_2 - 1$ 上，那么 $[\text{pos}_1, \text{pos}_2 - 1]$ 的 $\operatorname{MEX}$ 就大于 $2$ 了。

在 $a = [1, 3, 7, 6, 5, 0, 2, 4]$ 的情况下。

我们可以把 $3$ 放在 $(\text{pos}_1, \text{pos}_2)$ 的区间内。因为只有这样，才能满足所有的 $\operatorname{MEX}{[l, r]} > 3$ ，其中， $l \le\text{pos}_0, \text{pos}_1, \text{pos}_2 \le r$ ，并且除 $[l, r]$ 之外的所有区间， $\operatorname{MEX}$ 都小于 $3$ 。

也就是说，在 $a$ 中，如果一个区间包含了所有比 $3$ 小的数，就一定会包含 $3$ 。或者说，在 $a$ 中，不可能会有一个区间的 $\operatorname{MEX}$ 等于 $3$ ，而为了满足这一点，我们需要让 $3 \in (\text{pos}_1, \text{pos}_2)$ 。

我们设 $x$ 为 $\min{[\text{pos}_0 \ldots \text{pos}_3]}$ , $y$ 为 $\max{[\text{pos}_0 \ldots \text{pos}_3]}$ 。符合上面 $3 \in (\text{pos}_1, \text{pos}_2)$ 条件的位置就有 $(y - x + 1) - 3$ 个（ $-3$ 是因为区间中已经有 $0 \sim 2$ 了）。

现在我们可以从刚刚的观察中推广一下。我们刚刚发现如果在 $a$ 中，一个数在所有比他小的数的中间，那这个数就有很多位置可以放，相反，如果在所有比他小的数的外面，那就只能放在一个位置。

我们设正在考虑的数为 $k$ ， $x$ 为 $\min{[\text{pos}_0 \ldots \text{pos}_k]}$ ， $y$ 为 $\max{[\text{pos}_0 \ldots \text{pos}_k]}$ ，如果 $k$ 在 $[x, y]$ 这个区间外面，那么 $k$ 就只能放在 $\text{pos}_k$ 上，否则，可以选择 $[x, y]$ 中任意一个没被占用的地方放置。

我们设每个数能选的位置的数量为 $d_i$ ，那么最终的答案就是所有的 $d$ 乘起来，也就是 $\prod_{i = 0}^{n - 1}$

代码

在具体实现的时候，可以从 $0$ 开始~~一个一个~~的考虑，这样可以很方便的确定前面提到的 $x$ 和 $y$ ，以及 $[x,y]$ 区间内，被占用的位置的数量。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
// keywords:
const int MOD = 1e9 + 7;
int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        int a[n + 1];
        int pos[n + 1];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            pos[a[i]] = i;
        }
        ll l = pos[0], r = pos[0];
        ll ans = 1;
        for (int i = 1; i < n; i++) {
            // l 和 r 就是之前讲的 x, y
            if (pos[i] < l)
                l = pos[i];
            else if (pos[i] > r)
                r = pos[i];
                //如果在 x, y 的外面
            else
                ans = ans * (r - l + 1 - i) % MOD;
        }
        cout << ans << endl;
    }
}