题解：CF1909F1 Small Permutation Problem (Easy Version)

考虑将 a_i 差分，思考意义，可以将 a_i 放在二维平面的棋盘格上，第 i 列表示第 i 个位置，第 i 行表示元素的值，而排列中的元素就是可以放在棋盘上的点，每个点对应一个数。发现 a_i-a_{i-1} 为“排列前 i-1 位大于 i-1 的数和排列第 i 位的数”即一个 (1,i) 连到 (i,i) 再连到 (i,1) 的 L 形区域。又因为排列的意义等同于每行每列只能放一个数，因此这个 L 形区域里至多放两个数，即 a_i - a_{i-1} \le 2，分情况讨论（设可以放置的空行空列个数为 k)：

• 当 a_i-a_{i-1} = 0 时，说明 L 形区域没放元素，即可被放置元素的空行空列增加，k \Leftarrow k+1。

• 当 a_i - a_{i-1} = 1 时，说明在 L 形区域中放了一个元素，可以在之前统计出的空行空列中挑一行或一列放置，并且也可以在 L 形拐角放置，ans \Leftarrow ans \times (2k+1)。

• 当 a_i - a_{i-1} = 2 时，说明在 L 形区域中放了两个元素，即在第 i 行的空余格子内选一个，在第 i 列空余格子内再选一个，共 k^2 种，ans \Leftarrow ans \times k^2，k \Leftarrow k-1。

线性递推统计答案。

inline void work()
{
    n = read();
    a.resize(n+1);
    for(int i{1};i<=n;i++) a[i] = read();
    if(a[n] != n) {puts("0");return;}
    for(int i{1};i<=n;i++) if(a[i] > i) {puts("0");return;}
    int ans{1},k{};
    for(int i{1};i<=n;i++)
    {
        if(a[i] - a[i-1] == 0) k++;
        else if(a[i] - a[i-1] == 1) ans = ans * (2*k + 1) % MOD;
        else if(a[i] - a[i-1] == 2) (ans *= k * k % MOD) %= MOD,k--;
        else ans = 0;
    }
    writeln(ans);
}