The Shadow Array (Анализа на решението)

1. Unimodal Property

Recall that h_i = \min(L_i, R_i), where L_i is the prefix maximum and R_i is the suffix maximum of $a$. Since L_i is non-decreasing and R_i is non-increasing, their pointwise minimum $h$ must be unimodal (a mountain shape that increases or stays flat, reaches a maximum plateau, and then decreases or stays flat).

If $h$ does not satisfy this mountain structure, no valid original array $a$ exists, so the answer is immediately $0$.

2. Counting the Valid Arrays

Let P = \max(h) be the peak value, and let $L$ and $R$ be the first and last occurrences of $P$ in $h$. We can determine the number of valid choices for each a_i independently across three zones:

• Left Slope (1 \le i \le L):

  • For i = 1, we must have a_1 = h_1 ($1$ choice).

  • For 1 < i \le L, if h_i > h_{i-1}, a_i must push the prefix maximum up, so a_i = h_i ($1$ choice).

  • If h_i = h_{i-1}, a_i is bounded by the existing maximum, so a_i \in [1, h_i] (h_i choices).

• Plateau (L < i < R): For any element strictly between $L$ and $R$, both the prefix and suffix maximums are already guaranteed to be $P$. Thus, a_i can be any integer in $[1,P]$ ($P$ choices).

• Right Slope (R \le i \le n): Symmetrically from right to left:

  • For i = n, we must have a_n = h_n ($1$ choice).

  • For R \le i < n, if h_i > h_{i+1}, a_i = h_i ($1$ choice).

  • If h_i = h_{i+1}, a_i \in [1, h_i] (h_i choices).

3. Conclusion

The total number of valid arrays is the product of choices across all indices modulo 10^9 + 7.

Complexity: $\mathcal{O}(n)$ time and $\mathcal{O}(n)$ space per test case.