N-MEX (Counting Version)

First sanity checks

Let $a_0=n$. For the empty prefix, the $(n+1)$-mex is $n$, so this is the natural fake previous value.

For prefix $i$, we ask for the $k$-mex where

$$k=n-i+1.$$

With only $i$ chosen values, the $k$-mex cannot be below $k-1=n-i$, and because all $b_j$ are in $[0,n]$, it cannot exceed $n$. So every valid construction needs

$$n-i \le a_i \le n.$$

Also, $a_i$ cannot increase. If the old missing list has $a_{i-1}$ as its $(k+1)$-st element, then after one insertion and asking for the $k$-th element, the answer is either the old $k$-th missing number or still $a_{i-1}$. Never larger. Thus we need

$$a_i \le a_{i-1}.$$

If either check fails, the answer is $0$.

Source cross-check: official Codeforces tutorial implementation, https://codeforces.com/blog/entry/151886

The useful object

For prefix $i$, define $F_i$ as the set of the first $n-i+1$ missing numbers from $[0,n]$ after reading $b_1,\ldots,b_i$.

The condition says exactly:

$$|F_i|=n-i+1, \qquad \max(F_i)=a_i.$$

This is the whole trick. We do not need the full missing set, only this front chunk.

Now compare one step. Put $k=n-i+1$.

Before step $i$, $F_{i-1}$ has size $k+1$ and maximum $a_{i-1}$. After step $i$, $F_i$ has size $k$ and maximum $a_i$.

Case 1: $a_i<a_{i-1}$

The maximum decreased, so the removed element from the tracked missing set must be the old maximum $a_{i-1}$. Therefore $F_i$ is forced:

$$F_i=F_{i-1}\setminus\{a_{i-1}\}.$$

But the actual value $b_i$ only needs to avoid changing the first $k$ missing numbers. So $b_i$ can be any number not in $F_i$.

Since $F_i\subseteq[0,n]$ and $|F_i|=n-i+1$, the number of allowed values is

$$(n+1)-(n-i+1)=i.$$

So a decreasing step contributes a factor of $i$.

Case 2: $a_i=a_{i-1}$

The maximum stayed the same, so step $i$ removed some missing number smaller than $a_i$.

Counting this forward is annoying because future constraints decide which smaller values survive. So count the sets backwards. Starting from $F_i$, to recover $F_{i-1}$ we add one number $<a_i$ that is not already in $F_i$.

Inside $F_i$, there are exactly $n-i$ numbers smaller than $a_i$, because $F_i$ has size $n-i+1$ and its maximum is $a_i$. Among the $a_i$ numbers $0,1,\ldots,a_i-1$, the available choices are therefore

$$a_i-(n-i).$$

So an equal step contributes

$$a_i-(n-i).$$

That is the entire counting formula. Tiny, but it hides a slick reversal.

Final formula

With $a_0=n$, after validation:

$$\text{ans}=\prod_{i=1}^{n} \begin{cases} a_i-(n-i), & a_i=a_{i-1},\\ i, & a_i<a_{i-1}. \end{cases}$$

All products are taken modulo $10^9+7$.

Complexity

Each test case is just one scan:

$$O(n)$$

time and

$$O(1)$$

extra memory, ignoring the input array. Across all tests this is $O(\sum n)$, which is exactly what we want. No segment tree, no DP circus, no 2400-rated tax audit.