munte

Gigel lucrează într-un depozit şi trebuie să aşeze $n$ lăzi pe un singur rând. Înălţimile lăzilor pot să difere. Pentru a le gestiona mai uşor, Gigel a hotărât că le va aranja în formă de munte, astfel încât toate lăzile să fie vizibile fie din stânga, fie din dreapta, iar "vârful" să fie vizibil din ambele părţi. Gigel doreşte să afle în câte moduri distincte ar putea aranja cele $n$ lăzi astfel încât toate să fie vizibile. De exemplu, dacă avem $5$ lăzi cu înălţimile $2$, $1$, $3$, $2$, $4$, atunci există $4$ moduri de aranjare, după cum urmează:

Să observăm că, dacă în exemplul de mai sus am avea două lăzi de înălţime maximă $4$, Gigel nu ar putea aşeza lăzile în formă de munte, întrucât el doreşte ca vârful muntelui de lăzi să fie unic, iar înălţimile lăzilor de pe oricare latură a muntelui să fie un şir strict crescător.

Cerinţă

Realizaţi un program care determină numărul aranjărilor distincte posibile. Două aranjări sunt considerate distincte, dacă şirurile înălţimilor lăzilor diferă pe cel puţin o poziţie.

Date de intrare

Fişierul munte.in conţine pe prima linie numărul natural $n$ de lăzi, iar pe următoarele $n$ linii câte un număr natural reprezentând înălţimea unei lăzi.

Date de ieșire

Fişierul munte.out va conţine pe prima linie un singur număr, reprezentând numărul modalităţilor distincte de aranjare $\text{mod } 12 \ 343$.

Restricții și precizări

• $3 \leq n \leq 64 \ 000$
• $1 \leq$ înălţimile lăzilor $\leq 64 \ 000$

Exemplul 1

munte.in

5
3
1
3
2
4

munte.out

4

Exemplul 2

munte.in

4
2
4
4
2

munte.out

0