CF 1699C The Third Problem

有一個 $0..n-1$ 的排列 $a_i$。求有多少個排列 $b_i$ st 每一個 $[l, r]$，有 $\mathrm{MEX}_{i \in [l, r]} \left\{a_i\right\} = \mathrm{MEX}_{i \in [l, r]}\left\{b_i\right\}$。

令 $pos_i$ 表示 $i$ 在排列 $a$ 中的位置。考慮列舉 $\mathrm{MEX}_{j \in [l, r]} \left\{a_j\right\}$ 的值。如果 $\mathrm{MEX}_{j \in [l, r]}\left\{a_j\right\} = i$ 則 $a_{l..r}$ 一定包含了 $0..i-1$ 的所有值，因此這個 $l$，$r$ 應當滿足 $l \le \min_{j \in [0, i)} \left\{pos_j\right\}$ 且 $r \ge \mathrm{MEX}_{j \in [0, i)} \left\{pos_j\right\}$。同時，為了保證 $b$ 的 $\mathrm{MEX}$ 與 $a$ 相同，對於值 $i$，如果 $l \le pos_i \le r$，則在 $b$ 中，$i$ 可以放在 $[l, r]$ 的任意一個位置，否則必須放在與 $a$ 相同的位置。

void solve()
{
    int n;
    scanf("%d", &n);
    std::vector<int> a(n);
    for (auto &i : a) scanf("%d", &i);
    std::vector<int> pos(n);
    for (int i = 0; i < n; i++)
        pos[a[i]] = i;
    int l = pos[0], r = pos[0];
    long long ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (l <= pos[i] && pos[i] <= r) ans = ans * (r - l + 1 - i) % MODN; // 注意減去已經安排好位置的 i 個元素.
        l = std::min(l, pos[i]);
        r = std::max(r, pos[i]);
    }
    printf("%lld\n", ans);
}