思路

记 $b$ 是 $a$ 排列，且它们相似。$p_x$ 是 $x$ 在 $a$ 中的下标，$q_x$ 是 $x$ 在 $b$ 中的下标。

考虑 $q_0$，可以证明 $q_0$ 只能取 $p_0$。反证：若 $b_{p_0} > 0$，则 $MEX([b_{p_0}]) = 0$，而 $MEX([a_{p_0}]) = 1$，两者不等。

考虑 $q_1$，不妨设 $p_0 < p_1$，可以证明 $q_1$ 只能取 $p_1$。反证：

1. 若 $q_1 < p_1$，不妨设 $q_0 < q_1$，则 $MEX([b_{q_0}, \cdots, b_{q_1}]) \ge 2$，而 $MEX([a_{q_0}, \cdots, a_{q_1}]) = 1$，两者不等。
2. 若 $q_1 > p_1$，则 $MEX([b_{p_0}, \cdots, b_{p_1}]) = 1$，而 $MEX([a_{p_0}, \cdots, a_{p_1}]) \ge 2$，两者不等。

考虑 $q_2$。

1. 若 $p_2 \not \in (p_0, p_1)$，则 $q_2$ 只能取 $p_2$。反证：不妨设 $p_1 < p_2$：

   1. 若 $q_2 < p_2$，不妨设 $q_1 < q_2$，则 $MEX([b_{q_0}, \cdots, b_{q_2}]) \ge 3$，而 $MEX([a_{q_0}, \cdots, a_{q_2}]) = 2$，两者不等。
   2. 若 $q_2 > p_2$，则 $MEX([b_{p_0}, \cdots, b_{p_2}]) = 2$，而 $MEX([a_{p_0}, \cdots, a_{p_2}]) \ge 3$，两者不等。

2. 若 $p_2 \in (p_0, p_1)$，则 $q_2$ 可以取 $(p_0, p_1)$ 中的任何位置，共 $(p_1 - p_0 + 1) - 2$ 种可能。证明：

   1. $q_2$ 不能取 $(p_0, p_1)$ 之外的位置。反证：若 $q_2 < p_0$ 或 $q_2 > q_1$，则 $MEX([b_{p_0}, \cdots, b_{p_1}]) = 2$，而 $MEX([a_{p_0}, \cdots, a_{p_1}]) \ge 3$，两者不等。
   2. $q_2$ 可以取 $(p_0, p_1)$ 中的任何位置。
      1. 容易验证对于任意区间 $[l, r]$，当 $l < p_0 $ 或 $r > p_1$ 时，$MEX([b_{l}, \cdots, b_{r}]) = MEX([a_{l}, \cdots, a_{r}])$。
      2. 容易验证对于任意区间 $[l, r]$，当 $l = p_0 $ 或 $r = p_1$ 时，$MEX([b_{l}, \cdots, b_{r}]) = MEX([a_{l}, \cdots, a_{r}])$。

定义 $[l_i, r_i]$ 为包含 $q_0, \cdots, q_i$，共 $i + 1$ 个数的最小区间。

结论：若 $p_k \not \in (l_{k - 1}, r_{k - 1})$，则 $q_k$ 只能取 $p_k$。若 $p_k \in (l_{k - 1}, r_{k - 1})$，则 $q_k$ 有 $(r_{k - 1} - l_{k - 1} + 1) - k$ 种可能取值。$l_k = min(l_{k - 1}, p_k), r_k = max(r_{k - 1}, p_k)$。

引理：若集合 $S$ 中的任意元素 $x \in [0, n]$，且 $MEX(S) \le n$。若 $x > n$，则 $MEX(S + \{x\}) \le n$。

归纳法。

1. 当 $k = 1, 2$ 时，上文已证结论成立。
2. 假设当 $k = n$ 时，结论成立，则当 $k = n + 1$ 时：
   1. 若 $p_{n + 1} \not \in (l_{n}, r_{n})$，则 $q_{n + 1}$ 只能取 $p_{n + 1}$。反证：不妨设 $r_{n} < p_{n + 1}$：
      1. 若 $q_{n + 1} < p_{n + 1}$，不妨设 $r_n < q_{n + 1}$，则 $MEX([b_{l_n}, \cdots, b_{q_{n + 1}}]) \ge n + 2$，而 $MEX([a_{l_n}, \cdots, a_{q_{n + 1}}]) = n + 1$，两者不等。
      2. 若 $q_{n + 1} > p_{n + 1}$，则 $MEX([b_{l_n}, \cdots, b_{p_{n + 1}}]) = n + 1$，而 $MEX([a_{l_n}, \cdots, a_{p_{n + 1}}]) \ge n + 2$，两者不等。
   2. 若 $p_{n + 1} \in (l_{n}, r_{n})$，则 $q_{n + 1}$ 可以取 $(l_{n}, r_{n})$ 中的任何空闲位置，共 $(r_{n} - l_{n} + 1) - (n + 1)$ 种可能。
      1. $q_{n + 1}$ 不能取 $(l_{n}, r_{n})$ 之外的位置。反证：若 $q_{n + 1} < l_{n}$ 或 $q_{n + 1} > r_{n}$，则 $MEX([b_{l_{n}}, \cdots, b_{r_{n}}]) = n + 1$，而 $MEX([a_{l_{n}}, \cdots, a_{r_{n}}]) \ge n + 2$，两者不等。
      2. $q_{n + 1}$ 可以取 $(l_{n}, r_{n})$ 中的任何空闲位置。对于任意区间 $[L, R]$，根据假设，当 $k = n$ 时，$MEX([b_L, \cdots ,b_R]) = MEX([a_L, \cdots, a_R])$：
         1. 若 $[L, R]$ 与 $(l_{n}, r_{n})$ 无交集，则 $MEX([L, R])$ 不发生改变，现在仍然相等。
         2. 若 $[L, R]$ 等于 $[l_{n}, r_{n}]$，则 $a、b$ 同时在区间内增加了一个数 $n + 1$，因此 $MEX([b_L, \cdots ,b_R]) = MEX([a_L, \cdots, a_R]) \ge n + 2$。
         3. 若 $[L, R]$ 是 $[l_{n}, r_{n}]$ 的真子区间，由于当 $k = n$ 时，$MEX([b_L, \cdots ,b_R]) = MEX([a_L, \cdots, a_R]) \le n$，现在 $[L, R]$ 内可能包含 $n + 1$（或者不包含），由引理，现在 $MEX([L, R]) \le n$。因此当 $k = n + 1$ 时，$MEX([b_L, \cdots ,b_R]) = MEX([a_L, \cdots, a_R])$。

由此得证。

时间复杂度 $O(n)$。

#include <iostream>
#include <vector>

#define endl "\n"

using namespace std;

constexpr int MOD = 1e9 + 7;

void solve() {
  int n;
  cin >> n;
  vector<int> p(n);
  for (int i = 0, x; i < n; i++) {
    cin >> x;
    p[x] = i;
  }

  int ans = 1, l, r;
  for (int i = 1, l = r = p[0]; i < n; i++) {
    if (l < p[i] && p[i] < r) ans = ans * ((r - l + 1LL) - i) % MOD;
    l = min(l, p[i]);
    r = max(r, p[i]);
  }

  cout << ans << endl;
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}