proeminenta

Cea mai cunoscută măsură a unui vârf de munte este altitudinea sa. Vârfuri secundare ale unui munte înalt pot avea altitudini considerabile, dar în general acestea nu sunt atât de relevante. Din acest motiv, geografii au introdus o nouă măsură pentru un vârf: proeminenţa. Un profil este o reprezentare a altitudinilor în puncte succesive, între care ne putem deplasa la stânga sau dreapta.

În desen avem profilul munţilor Făgăraş, pe care exemplificăm următoarele definiţii:

1. Un vârf este un punct (sau o succesiune de puncte consecutive cu aceeaşi altitudine), pentru care altitudinile punctelor alăturate în stânga, respectiv în dreapta sunt strict mai mici decât altitudinea vârfului. De exemplu, Negoiu este un vârf (altitudinea sa este $2535m$, punctul de pe profil situat în stânga sa are altitudinea $2306m$, iar punctul de pe profil situat în dreapta sa are altitudinea $2030m$). Un alt exemplu de vârf este Urlea, fiind reprezentat pe profil prin două puncte consecutive cu altitudinea $2473m$, având în stânga un punct cu altitudinea $2160m$, iar în dreapta un punct cu altitudinea $1511m$.
2. Cea mai adâncă vale dintre două vârfuri este altitudinea minimă a unui punct care se află între cele două vârfuri. De exemplu, în desen între Negoiu şi Moldoveanu cea mai adâncă vale este la 2030m.
3. Proeminenţa unui vârf este diferenţa minimă dintre altitudinea lui şi cea mai adâncă vale dintre el şi un vârf strict mai înalt decât el. Dacă nu există un vârf strict mai înalt, proeminenţa este altitudinea vârfului. De exemplu, pentru a determina proeminenţa vârfului Gălăşescu Mare putem considera vârfurile strict mai înalte (în ordine de la stânga la dreapta: Negoiu, Moldoveanu şi Urlea). Dacă plecăm de pe Negoiu, diferenţa dintre cea mai adâncă vale şi Gălăşescu Mare este $2470-2030=440m$. Dacă plecăm de pe Moldoveanu, diferenţa dintre cea mai adâncă vale şi Gălăşescu Mare este $2470-2213=257m$. Dacă plecăm de pe Urlea, diferenţa dintre cea mai adâncă vale şi Gălăşescu Mare este $2470-2160=310m$. Diferenţa minimă este $257m$, deci proeminenţa vârfului Gălăşescu Mare este dată de vârful Moldoveanu.

Cerințe

Scrieţi un program care, cunoscând configuraţia unui profil, rezolvă următoarele două cerinţe:

1. determină numărul de vârfuri existente pe profilul respectiv;
2. determină proeminenţa fiecărui vârf de pe profil.

Date de intrare

Fișierul de intrare proeminenta.in conține pe prima linie numărul natural $C$, reprezentând cerinţa care trebuie să fie rezolvată: $1$ sau $2$. Pe cea de a doua linie se află numărul natural $N$, reprezentând numărul de puncte din profil. Pe a treia linie se află N numere naturale separate prin câte un spaţiu $a_1, a_2, \dots, a_N$, reprezentând altitudinile celor $N$ puncte de pe profil, în ordine de la stânga la dreapta.

Date de ieșire

Fișierul de ieșire proeminenta.out va conține o singură linie pe care va fi scris răspunsul la cerinţa $C$. Dacă $C = 1$ răspunsul va fi numărul natural $Nr$, reprezentând numărul de vârfuri. Dacă $C = 2$ răspunsul va fi o succesiune de $Nr$ valori naturale separate prin câte un singur spaţiu, reprezentând proeminenţele celor $Nr$ vârfuri, în ordinea din fişierul de intrare.

Restricții și precizări

• $3 \leq N \leq 10^6$;
• $0 \leq a_i < 2^{31}$, pentru $1 \leq i \leq N$;
• $a_1 < a_2$ și $a_{N-1} > a_N$;

Exemplul 1

proeminenta.in

1
19
1387 1890 2306 2535 2030 2391 2079
2544 2213 2470 2305 2433 2160 2473
2473 1511 1735 1621 1367

proeminenta.out

7

Exemplul 2

proeminenta.in

2
19
1387 1890 2306 2535 2030 2391 2079
2544 2213 2470 2305 2433 2160 2473
2473 1511 1735 1621 1367

proeminenta.out

505 312 2544 257 128 313 224

Explicație

Profilul din fişierele de intrare este cel reprezentat în desen. Cele 7 vârfuri sunt denumite pe desen. Deși altitudinile apar în tabel pe mai multe linii, ele vor fi scrise pe o singură linie în fișierul de intrare.