Munte5

munte5

== include(page="template/taskheader" task_id="munte5") ==

Gigel lucreaza intr-un depozit si trebuie sa aseze $n$ lazi pe un singur rand. Inaltimile lazilor pot sa difere. Pentru a le gestiona mai usor, Gigel a hotarat ca le va aranja in forma de munte, astfel incat toate lazile sa fie vizibile fie din stanga, fie din dreapta, iar "varful" sa fie vizibil din ambele parti. Gigel doreste sa afle in cate moduri distincte ar putea aranja cele $n$ lazi astfel ca toate sa fie vizibile. De exemplu, daca avem $5$ lazi cu inaltimile $2$, $1$, $3$, $2$, $4$ atunci exista $4$ moduri de aranjare, dupa cum urmeaza:
 
1 2 3 4 2;  1 2 4 3 2;  2 3 4 2 1;  2 4 3 2 1
 
Sa observam ca, daca in exemplul de mai sus am avea doua lazi de inaltime maxima $4$, Gigel nu ar putea aseza lazile in forma de munte, intrucat el doreste ca varful muntelui de lazi sa fie unic, iar inaltimile lazilor de pe oricare latura a muntelui sa fie un sir strict crescator.
 
h2. Cerinta
 
Realizati un program care determina numarul aranjarilor distincte posibile. Doua aranjari sunt considerate distincte, daca sirurile inaltimilor lazilor difera pe cel putin o pozitie.
 

Poveste si cerinta...

h2. Date de intrare

Fisierul de intrare $munte5.in$ contine pe prima linie numarul natural $n$ de lazi, iar pe urmatoarele $n$ linii cate un numar natural reprezentand inaltimea unei lazi.

Fisierul de intrare $munte5.in$ ...

h2. Date de iesire

Fisierul de iesire $munte5.out$ va contine pe prima linie un singur numar, reprezentand numarul modalitatilor distincte de aranjare modulo $12343$.

In fisierul de iesire $munte5.out$ ...

h2. Restrictii

* $3 ≤ n ≤ 64.000$
* $1 ≤ inaltimile lazilor   ≤ 64.000$
* Un munte nu poate fi strict crescator sau descrescator

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. munte5.in |_. munte5.out |

| 5
  3
  1
  3
  2
  4
| 4

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

| 4
  2
  4
  4
  2
| 0
|

h3. Explicatie

== include(page="template/taskfooter" task_id="munte5") ==

...
== include(page="template/taskfooter" task_id="munte5") ==

3341