Yana, Mino, White y Huzz son mejores amigos.
Habiendo terminado por fin las exigentes tareas del entrenador, Huzz se había ganado un descanso. Lo encontró en una tarde perezosa, donde el mundo parecía avanzar a paso de tortuga, envuelto en la cálida bruma dorada del atardecer inminente. Una suave brisa apenas hacía más que agitar las motas de polvo que bailaban en los rayos de sol que se filtraban oblicuamente entre las hojas de un gran roble.
En ese vacío somnoliento y confortable, Huzz encontró una permutación en su suave peluche de tiburón. Decidió compartirla con sus amigos por diversión.
A Mino le encanta dividir. Puede dividir esta permutación en varios segmentos contiguos.
A Yana le encanta intercambiar. Puede elegir un segmento contiguo e intercambiar sus elementos máximo y mínimo.
Específicamente, pueden realizar los siguientes dos tipos de operaciones cualquier número de veces, en cualquier orden:
- split: Elegir un segmento contiguo cuya longitud sea mayor que $1$. Luego elegir una posición dentro de él y dividirlo en dos segmentos contiguos adyacentes. Por ejemplo, $(a_i, \dots, a_j)$ se puede dividir en $(a_i, \dots, a_k)$ y $(a_{k+1}, \dots, a_j)$, donde $i \le k < j$.
- swap: Elegir un segmento contiguo e intercambiar sus elementos máximo y mínimo.
Después de realizar cualquier número de operaciones, dejan de operar y todos los segmentos resultantes se fusionan en su orden original para formar una nueva permutación.
A White le encanta contar. Se pregunta: ¿cuántas permutaciones distintas pueden obtener?
Como el resultado puede ser muy grande, solo necesitas hallar la respuesta módulo $998\,244\,353$.
Entrada
La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 500$), la longitud de la permutación.
La segunda línea contiene $n$ enteros $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), que representan la permutación misma. Se garantiza que $\{a_n\}$ es una permutación.
Salida
Imprime un entero, el número de permutaciones distintas que pueden obtener módulo $998\,244\,353$.
Ejemplos
Entrada
4 1 4 2 3
Salida
10
Entrada
7 5 1 4 2 6 3 7
Salida
340
Nota
En el primer ejemplo, las siguientes son todas las permutaciones posibles que pueden obtener:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$