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

h2. Cerinţă
După ce şi-a cumpărat noua casă Ştefan a hotărât să refacă gardul din faţa sa. Acesta este format din N scânduri de înălţimi distincte, aşezate una lângă alta. De fapt valorile înălţimilor scândurilor formează o permutare a numerelor de la 1 la N. Unele scânduri sunt speciale, şi pe ele nu le poate muta din loc. Acestea sunt cele din care poate vedea extremitatea stângă (de la începutul gardului până la o astfel de scândură nu se află alta mai înaltă). Oricare din celelalte scânduri poate fi mutată (interschimbată cu alta) dar cele două trebuie să rămână între aceleaşi scânduri speciale ca şi înainte de mutare. Odată schimbate între ele astfel de scânduri, se obţine o configuraţie nouă de gard. Costul unei configuraţii se calculează însumând costul de la fiecare scândură din acea configuraţie. Costul unei scânduri se calculează astfel: dacă scândura este specială, costul său este 0. Dacă scândura de pe poziţia i nu este specială, costul său este modul(h[i]-h[i-1]) + modul(h[i]-h[i+1]), unde h[i] = înălţimea scândurei de pe poziţia i. Considerăm că pe poziţia 0 este o scândură fictivă cu înălţimea 0 iar pe poziţia n+1 este o scândură fictivă cu înălţimea n+1 (ambele considerate speciale).

După ce şi-a cumpărat noua casă Ştefan a hotărât să refacă gardul din faţa sa. Acesta este format din $N$ scânduri de înălţimi distincte, aşezate una lângă alta. De fapt valorile înălţimilor scândurilor formează o permutare a numerelor de la $1$ la $N$. Unele scânduri sunt speciale, şi pe ele nu le poate muta din loc. Acestea sunt cele din care poate vedea extremitatea stângă: de la începutul gardului până la o astfel de scândură nu se află alta mai înaltă. Oricare din celelalte scânduri poate fi mutată (interschimbată cu alta) dar cele două trebuie să rămână între aceleaşi scânduri speciale ca şi înainte de mutare. Odată schimbate între ele astfel de scânduri, se obţine o configuraţie nouă de gard. Costul unei configuraţii se calculează însumând costul de la fiecare scândură din acea configuraţie. Costul unei scânduri se calculează astfel: dacă scândura este specială, costul său este $0$. Dacă scândura de pe poziţia $i$ nu este specială, costul său este $|h[i]-h[i-1]| + |h[i]-h[i+1]|$, unde $h[i]$ = înălţimea scândurei de pe poziţia $i$. Considerăm că pe poziţia $0$ este o scândură fictivă cu înălţimea $0$ iar pe poziţia $n+1$ este o scândură fictivă cu înălţimea $n+1$ (ambele considerate speciale).

Determinaţi numărul de configuraţii distincte de cost minim ce se pot obţine.

Determinaţi costul minim al unei configuratii care se poate obtine in modul descris, precum si numărul de configuraţii distincte de cost minim.

h2. Date de intrare

Pe prima linie a fişierului gard.in se găseşte un număr natural N, reprezentând lungimea gardului. Pe linia a 2-a se găsesc înălţimile celor N scânduri, în ordine de la stânga la dreapta.

Pe prima linie a fişierului $gard5.in$ se găseşte un număr natural $N$, reprezentând lungimea gardului. Pe linia a 2-a se găsesc înălţimile celor $N$ scânduri, în ordine de la stânga la dreapta.

h2. Date de ieşire

Pe prima linie a fişierului gard.out se află un număr ce reprezintă numărul de configuraţii de cost minim.

Pe prima linie a fişierului $gard5.out$ se află doua numere: primul reprezintă costul minim posibil al unei configuraţii, iar al doilea reprezintă numărul de configuraţii de cost minim.

h2. Restricţii
* $1 ≤ N ≤ 100$

* Numărul cerut poate fi memorat într-o variabilă de tip long long

* Numărul cerut poate fi memorat într-o variabilă pe 64 de biţi cu semn

* Dacă are costul minim, şi configuraţia dată se numără

* Costul minim valorează $50%$ din punctaj, iar numărul de configuraţii de cost minim restul de $50%$

h2. Exemplu
table(example). |_. gard5.in |_. gard5.out |
| 5
  1 2 3 4 5

| 1

| 0 1 |
| 4
  1 4 2 3
| 6 2

|
h3. Explicaţie