The content below was generated entirely by machine translation. Please verify its accuracy. If anything is unclear, consult the Chinese source version.

Problem links: (CF, Luogu) | I strongly recommend reading it on the blog.

This problem is genuinely difficult to think of. I spent a long time reading the Codeforces solution before understanding it (I am too inexperienced).

Problem Statement

Given a permutation $a$ of length $n$ , find how many permutations $b$ of the same length are similar to $a$ .

If, for every interval $[l, r] (1 \le l \le r \le n)$ , the following condition holds:

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

then permutations $a$ and $b$ are called similar.

Here, for an array $c$ , $\operatorname{MEX}$ is defined as the smallest non-negative integer $x$ that does not appear in $c$ .

For example, $\operatorname{MEX}([1,2,3,4,5]) = 0$ and $\operatorname{MEX}([0,1,2,4,5]) = 3$ .

Because the answer may be large, print it modulo $10^9 + 7$ .

Approach

It may be difficult to think of the answer directly, so first simulate the sample and try to construct some $b$ .

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

Begin by considering the number $0$ in the sample. We can see that the position of $0$ in $b$ must be the same as its position in $a$ .

Let the position of $i$ in $a$ be $\text{pos}_i$ ; for example, $\text{pos}_0 = 6$ (indices start from 1).

Compare the MEX values of $a$ and $b$ on the interval $[\text{pos}_0, \text{pos}_0]$ . In $a$ , because $a[\text{pos}_0] = 0$ , we have $\operatorname{MEX}([\text{pos}_0]) = 1$ .

If the position of $0$ in $b$ changed, then because $a[\text{pos}_0] > 0$ , the MEX of this interval in $b$ would be $0$ .

Thus, the position of $0$ cannot change.

We can also conclude that the position of $1$ cannot change.

Consider the intervals $[\text{pos}_1(1), \text{pos}_0(6)] (1\ 3\ 7\ 2\ 5\ 0)$ and $[\text{pos}_1 + 1, \text{pos}_0](3\ 7\ 2\ 5\ 0)$ .

Because $1$ is present, $\operatorname{MEX}([\text{pos}_1, \text{pos}_0])$ is greater than $1$ . Because $0$ is present and $1$ is absent, $\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0])$ is exactly $1$ .

Suppose that we changed the position of $1$ in $b$ , for example moving it to position $2$ . Then $\operatorname{MEX}([\text{pos}_1 + 1, \text{pos}_0](1\ 7\ 2\ 5\ 0)$ in $b$ would be greater than $1$ , which does not match the value $1$ in $a$ .

Now consider where $2$ can be placed legally. If $2 \in (\text{pos}_1, \text{pos}_0)$ in $a$ , then in $b$ , $2$ can be placed at any position in the interval $(\text{pos}_1, \text{pos}_0)$ .

Let $[l, r]$ be an interval in $a$ containing $0$ and $1$ , namely $l \le \text{pos}_1, \text{pos}_0 \le r$ .

Because $2 \in (\text{pos}_1, \text{pos}_0)$ in $a$ , every such interval has MEX greater than $2$ (an interval containing both $0$ and $1$ also contains $2$ ).

At the same time, every other interval in $a$ that does not satisfy $l \le \text{pos}_1, \text{pos}_0 \le r$ has MEX at most $1$ (such an interval contains at most one $0$ , so its MEX is $1$ ).

Therefore, as long as $2 \in (\text{pos}_1, \text{pos}_0)$ in $b$ , we still have $\operatorname{MEX}([l,r]) > 2$ . Keeping every other number in place preserves similarity between $a$ and $b$ .

There are $(\text{pos}_0 - \text{pos}_1 + 1) - 2$ such positions; the $-2$ accounts for the positions already occupied by $0$ and $1$ .

What if $2 \notin (\text{pos}_1, \text{pos}_0)$ in $a$ ?

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

As with $0$ and $1$ , we can conclude that, in this case, $2$ must be placed at the same position in $b$ .

Consider $[\text{pos}_1, \text{pos}_2]$ , whose MEX is greater than $2$ , and $[\text{pos}_1, \text{pos}_2 - 1]$ , whose MEX is exactly $2$ (it contains $0$ and $1$ ).

If we place $2$ at $\text{pos}_2 - 1$ , the MEX of $[\text{pos}_1, \text{pos}_2 - 1]$ becomes greater than $2$ .

In $a = [1, 3, 7, 6, 5, 0, 2, 4]$ , we can place $3$ anywhere in $(\text{pos}_1, \text{pos}_2)$ . Only in this way can we ensure $\operatorname{MEX}[l,r] > 3$ whenever $l \le\text{pos}_0, \text{pos}_1, \text{pos}_2 \le r$ , while all other intervals have MEX less than $3$ .

In other words, if an interval in $a$ contains every number smaller than $3$ , it must contain $3$ . Equivalently, there cannot be an interval whose MEX is $3$ , so we need $3 \in (\text{pos}_1, \text{pos}_2)$ .

Let $x = \min{[\text{pos}_0 \ldots \text{pos}_3]}$ and $y = \max{[\text{pos}_0 \ldots \text{pos}_3]}$ . The number of positions satisfying $3 \in (\text{pos}_1, \text{pos}_2)$ is $(y - x + 1) - 3$ ; the $-3$ accounts for the positions already occupied by $0 \sim 2$ .

We can generalize this observation. If a number in $a$ lies between all numbers smaller than it, it has many possible positions. If it lies outside all smaller numbers, it can only stay in its original position.

Let the number currently under consideration be $k$ , $x = \min{[\text{pos}_0 \ldots \text{pos}_k]}$ , and $y = \max{[\text{pos}_0 \ldots \text{pos}_k]}$ . If $k$ is outside $[x,y]$ , it can only be placed at $\text{pos}_k$ ; otherwise, it can be placed in any unoccupied position in $[x,y]$ .

Let $d_i$ be the number of positions available for each number. The final answer is the product of all $d$ , namely $\prod_{i = 0}^{n - 1}$ .

Code

In the implementation, consider the numbers from $0$ onward one by one. This conveniently determines the $x$ and $y$ mentioned above and the number of occupied positions in $[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 and r are the x and y described above.
            if (pos[i] < l)
                l = pos[i];
            else if (pos[i] > r)
                r = pos[i];
                // Outside x and y.
            else
                ans = ans * (r - l + 1 - i) % MOD;
        }
        cout << ans << endl;
    }
}