Yana, Mino, White e Huzz sono migliori amici.
Avendo finalmente portato a termine gli impegnativi compiti dell'allenatore, Huzz si era guadagnato un po' di riposo. Lo trovò in un pigro pomeriggio, in cui il mondo sembrava rallentare fino quasi a fermarsi, avvolto nella calda foschia dorata del crepuscolo imminente. Una leggera brezza faceva poco più che smuovere i granelli di polvere che danzavano nei raggi di sole che filtravano obliqui tra le foglie di una grande quercia.
In quel vuoto assonnato e confortevole, Huzz trovò una permutazione nel suo morbido squalo di peluche. Decise di condividerla con i suoi amici per divertimento.
Mino ama dividere. Può dividere questa permutazione in diversi segmenti contigui.
Yana ama scambiare. Può scegliere un segmento contiguo e scambiare il suo elemento massimo e il suo elemento minimo.
Nello specifico, possono eseguire i seguenti due tipi di operazioni un numero qualsiasi di volte, in qualsiasi ordine:
- split: Scegliere un segmento contiguo la cui lunghezza è maggiore di $1$. Poi scegliere una posizione al suo interno e dividerlo in due segmenti contigui adiacenti. Ad esempio, $(a_i, \dots, a_j)$ può essere diviso in $(a_i, \dots, a_k)$ e $(a_{k+1}, \dots, a_j)$, dove $i \le k < j$.
- swap: Scegliere un segmento contiguo e scambiare i suoi elementi massimo e minimo.
Dopo aver eseguito un numero qualsiasi di operazioni, si fermano e tutti i segmenti risultanti vengono uniti nel loro ordine originale per formare una nuova permutazione.
White ama contare. Si chiede: quante permutazioni distinte possono ottenere?
Poiché il risultato può essere molto grande, devi solo trovare la risposta modulo $998\,244\,353$.
Input
La prima riga dell'input contiene un intero $n$ ($1 \le n \le 500$), la lunghezza della permutazione.
La seconda riga contiene $n$ interi $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$), che rappresentano la permutazione stessa. È garantito che $\{a_n\}$ è una permutazione.
Output
Stampa un intero, il numero di permutazioni distinte che possono ottenere modulo $998\,244\,353$.
Esempi
Input
4 1 4 2 3
Output
10
Input
7 5 1 4 2 6 3 7
Output
340
Note
Nel primo esempio, le seguenti sono tutte le possibili permutazioni che possono ottenere:
$(1234), (1243), (1423), (1432), (4123), (4132), (4213), (4231), (4312), (4321)$