Pracsiu Dan (dnprx) 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:
- 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.
- 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.
- 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ța
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], …, 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 ≤ N ≤ 1.000.0000 ≤ a[i] < 231, pentru1 ≤ i ≤ Na[1] < a[2]șia[N-1] > a[N]- Datorită dimensiunii testelor, unele nu au fost incluse
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
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.
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