Тіньовий масив (Розбір)

1. Властивість монотонного горба

Нагадаємо, що h_i = \min(L_i, R_i), де L_i — префіксний максимум, а R_i — суфіксний максимум масиву $a$. Оскільки L_i є неспадною, а R_i — незростаючою, їхня покомпонентна мінімальна функція $h$ обов'язково є монотонним горбом (формою гори, яка зростає або лишається сталою, досягає плато максимуму, а потім спадає або лишається сталою).

Якщо $h$ не має такої гірської структури, жодного допустимого початкового масиву $a$ не існує, тому відповідь одразу дорівнює $0$.

2. Підрахунок допустимих масивів

Нехай P = \max(h) — значення піка, а $L$ і $R$ — перша та остання позиції, де в $h$ зустрічається $P$. Ми можемо визначити кількість допустимих виборів для кожного a_i незалежно в трьох зонах:

• Ліва схилова частина (1 \le i \le L):

  • Для i = 1 маємо a_1 = h_1 ($1$ варіант).

  • Для 1 < i \le L, якщо h_i > h_{i-1}, то a_i має підняти префіксний максимум, отже a_i = h_i ($1$ варіант).

  • Якщо h_i = h_{i-1}, то a_i обмежене вже наявним максимумом, тому a_i \in [1, h_i] (h_i варіантів).

• Плато (L < i < R): Для будь-якого елемента строго між $L$ та $R$ і префіксний, і суфіксний максимуми вже гарантовано дорівнюють $P$. Отже, a_i може бути будь-яким цілим числом з $[1,P]$ ($P$ варіантів).

• Права схилова частина (R \le i \le n): Симетрично справа наліво:

  • Для i = n маємо a_n = h_n ($1$ варіант).

  • Для R \le i < n, якщо h_i > h_{i+1}, то a_i = h_i ($1$ варіант).

  • Якщо h_i = h_{i+1}, то a_i \in [1, h_i] (h_i варіантів).

3. Висновок

Загальна кількість допустимих масивів дорівнює добутку кількості варіантів для всіх індексів за модулем 10^9 + 7.

Складність: $\mathcal{O}(n)$ часу та $\mathcal{O}(n)$ пам'яті на кожен набір вхідних даних.