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

Poveste şi cerinţă...

{!>problema/copaci4?x.jpg!}
 
p<>. Se consideră $n$ copaci de diferite înălţimi, aflaţi în linie dreaptă la distanţe egale, numerotaţi de la $1$ la $n$. Pentru fiecare copac se cunoaşte înălţimea sa $H$~$i$~. Cum şi copacii simt nevoia să socializeze, fiecare dintre ei are prieteni printre ceilalţi copaci. Prietenii oricărui copac $i$ se pot afla atât la stânga, cât şi la dreapta sa. Relaţiile de prietenie sunt definite în felul următor: pentru fiecare copac $i$ considerăm un şir $d$~$1$~, $d$~$2$~, ..., $d$~$x$~ reprezentând prietenii copacului $i$ situaţi în dreapta sa şi un şir $s$~$1$~, $s$~$2$~ ... $s$~$y$~ reprezentând prietenii copacului $i$ situaţi în stânga acestuia. Copacii din cele două şiruri corespunzătoare unui copac $i$ formează împreună lista prietenilor acestuia. Şirurile corespunzătoare copacului $i$ se definesc astfel:
 
# • $d$~$1$~ $= i + 1$ (dacă $i = n$, atunci copacul $i$ nu are niciun prieten la dreapta sa, şirul rămânând vid);
 • pentru fiecare $k &ge; 2$, $d$~$k$~ este cel mai mic indice $(1 &le; d$~$k$~ $&le; n)$ cu proprietatea că $d$~$k$~ > $d$~$k-1$~ şi $H$~$dk$~ > $H$~$dk-1$~. Dacă $d$~$k$~ nu există, atunci lista de prieteni la dreapta ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.
 
# • $s$~$1$~ $= i - 1$ (daca $i = 1$, atunci copacul $i$ nu are niciun prieten la stânga sa, sirul rămânând vid);
 • pentru fiecare $k &ge; 2$, $s$~$k$~ este cel mai mare indice $(1 &le; s$~$k$~ $&le; n)$ cu proprietatea că $s$~$k$~ < $s$~$k-1$~ şi $H$~$sk$~ > $H$ ~$sk-1$~. Dacă $s$~$k$~ nu există, atunci lista de prieteni la stânga ai copacului $i$ s-a încheiat şi construirea şirului se opreşte la acest pas.

h2. Date de intrare