Fișierul intrare/ieșire copaci.in, copaci.out Sursă Concurs Infogim 2018 clasele 6-8
Autor Liana Tucar Adăugată de avatar ptest Hai la Olimpiada - Iasi Gimnaziu ptest
Timp de execuție pe test 0.5 sec Limită de memorie 16384 KB
Scorul tău N/A Dificultate N/A
open book Poți vedea testele pentru această problemă accesând atașamentele .

Copaci

Magdozaur este un monstruleț cu un rafinat gust estetic. Ea a plantat N copaci (de înălțimi distincte două câte două) aliniați frumos într-o linie de la stânga la dreapta spre vale. A venit momentul să-i tundă (pentru a le reda forma perfectă). Deoarece are o macara mai complicată, ea tunde copacii repetând următoarea operație: alege copacul de înălțime maximă, și folosește macaraua pentru a tunde acel copac si toți copacii din drepata lui care n-au fost deja tunși (fiindcă e ușor sa conducă la vale). Repetă aceasta operație până când a tuns toți copacii.

Magdozaur vă zice înălțimile copacilor de la stânga la dreapta (deal spre vale) și vă roagă să-i spuneți câte operații trebuie să facă pentru a-și reface grădina perfetă (a tunde toți copacii). Deoarece tocmai și-a luat carnetul de conducere, este darnică și vă va rasplăti cu 100 de puncte dacă o ajutați.

Date de intrare

În fișierul copaci.in se află pe prima linie numărul N reprezentând numărul de copaci. Pe a doua linie se află N numere naturale distincte reprezentând înălțimile copacilor.

Date de ieșire

Afișați pe prima linie în fișierul copaci.out numărul de operații necesare pentru a tunde toți copacii.

Restricții

  • 1 ≤ N ≤ 100.000
  • Înălțimile copacilor sunt numere naturale ≤ 1010

Exemplu

copaci.in copaci.out
11
2 8 1 9 60 57 3 100 5 4 70
5

Explicație

Operatia 1:
2 8 1 9 60 57 3 100 5 4 70
Înălțimea 100 este maximă. Tunde toți copacii din dreapta sa

Operatia 2:
2 8 1 9 60 57 3
Înălțimea 60 este maximă dintre copacii ne-tunși. Tunde toți copacii
din dreapta sa

Operatia 3:
2 8 1 9
Înălțimea 9 este maximă dintre copacii ne-tunși. Tunde toți copacii
din dreapta sa

Operatia 4:
2 8 1
Înălțimea 8 este maximă dintre copacii ne-tunși. Tunde toți copacii

Operatia 5:
2
Înălțimea 2 este maximă dintre copacii ne-tunși. Tunde toti copacii
din dreapta sa. Acum toți copacii sunt tunși.

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 2 categorii