[C++知识库]C. The Third Problem(MEX，思维，组合数)[Codeforces Round #804 (Div. 2)]

题面如下：

思路or题解

因为是$MEX$问题，我们可以通过维护每一个数的 $[l,r]$ 来进行求解
如果 $k$ 维护的范围是 $[l,r]$
那么我们在计算 $k+1$ 的时候可以发现：
在$[l+1,r?1]$ 如果 $k+1$ 的位置满足在里面，那么 $k+1$ 放这个区间的任意一个位置都是满足题意的；如果不在这个区间那么 $k+1$ 的位置是唯一的，就是原数组 $k+1$ 的位置

AC代码如下：

const int mod = 1e9 + 7;
const int N = 100009;
int n, s[N], pos[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i], pos[s[i]] = i;
    
    int l = 0x3f3f3f3f, r = -1;
    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        if (pos[i] > l && pos[i] < r)
            ans = (ll)ans * (r - l + 1 - i) % mod;
        l = min(l, pos[i]), r = max(r, pos[i]);
    }

    cout << ans << '\n';
}
int main()
{
    buff;
    int _;
    cin >> _;
    while (_--)
        solve();
}